六、图结构

文章目录

• 一、引入
• 二、基本概念
• 三、图的表示
• 四、图的遍历
• • 4.1 图的深度优先遍历（DFS）
  • 4.2 图的广度优先遍历（BFS）
  • 4.3 图的深度优先 VS 广度优先

一、引入

二、基本概念

三、图的表示

package com.gyh.grapg;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author Gao YongHao
 * @version 1.0
 */
public class Graph {
    private ArrayList<String> vertexList; // 存储顶点的集合
    private int[][] edges; // 领接矩阵
    private int numOfEdges = 0;// 表示边的数目

    public static void main(String[] args) {
        int n = 5;
        String[] VertexValue = {"A", "B", "C", "D", "E"};
        // 创建图对象
        Graph graph = new Graph(5);
        for (String s : VertexValue) {
            graph.insertVertex(s);
        }
        // 添加边
        graph.insertEdge(0,1,1);
        graph.insertEdge(0,2,1);
        graph.insertEdge(1,2,1);
        graph.insertEdge(1,3,1);
        graph.insertEdge(1,4,1);

        // 显示邻接矩阵
        graph.showGraph();


    }

    public Graph(int n) {
        this.edges = new int[n][n];
        vertexList = new ArrayList<>();
    }

    // 图中常用的能方法
    // 返回结点的个数
    public int getNumOfVertex() {
        return vertexList.size();
    }

    // 返回边的个数
    public int getNumOfEdges() {
        return numOfEdges;
    }

    // 显示图对应的矩阵
    public void showGraph() {
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }
    }

    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    // 添加结点
    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }

    // 添加边
    public void insertEdge(int v1, int v2, int weight) {
        if (v1 >= edges.length || v2 >= edges.length) {
            throw new RuntimeException("该结点标号越界");
        }
        // 考虑无向图
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }

}

四、图的遍历

4.1 图的深度优先遍历（DFS）

4.2 图的广度优先遍历（BFS）

package com.gyh.grapg;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Gao YongHao
 * @version 1.0
 */
public class Graph {
    private ArrayList<String> vertexList; // 存储顶点的集合
    private int[][] edges; // 领接矩阵
    private int numOfEdges = 0;// 表示边的数目
    // 定义数组boolean[]，记录某个结点是否被访问过
    private boolean[] isVisited;

    public static void main(String[] args) {
        int n = 5;
        String[] VertexValue = {"A", "B", "C", "D", "E"};
        // 创建图对象
        Graph graph = new Graph(n);
        for (String s : VertexValue) {
            graph.insertVertex(s);
        }
        // 添加边
        graph.insertEdge(0, 1, 1);
        graph.insertEdge(0, 2, 1);
        graph.insertEdge(1, 2, 1);
        graph.insertEdge(1, 3, 1);
        graph.insertEdge(1, 4, 1);

        // 显示邻接矩阵
        graph.showGraph();
        // 深度优先搜索
//        graph.dfs(0);

        // 广度优先搜索
        graph.bfs(2, new LinkedList<>());

    }

    /**
     * 广度优先遍历(借助队列实现)
     *
     * @param v 起始位置
     */
    public void bfs(int v, Queue<Integer> queue) {
        // 打印当前结点
        queue.add(v);
        isVisited[v] = true;
        while (queue.size() > 0) {
            v = queue.poll();
            System.out.println(vertexList.get(v));

            // 将同一层中各未遍历过的结点下标加入至队列
            for (int i = 0; i < edges.length; i++) {
                if (edges[v][i] != 0 && !isVisited[i]) {
                    queue.add(i);
                    isVisited[i] = true; // 加入队列时即设置已访问，不设置可能重复加入队列
                }
            }
        }
    }

    /**
     * 深度优先遍历
     *
     * @param v 起始位置
     */
    public void dfs(int v) {
        if (v < 0 || v >= edges.length) {
            return;
        }
        // 打印当前信息(遍历后则设置已经遍历)
        System.out.println(vertexList.get(v));
        isVisited[v] = true;

        // 对其所有的邻接结点进行轮询的递归遍历
        for (int i = 0; i < edges.length; i++) {
            if (edges[v][i] != 0 && !isVisited[i]) {
                dfs(i);
            }
        }

    }

    public Graph(int n) {
        this.edges = new int[n][n];
        vertexList = new ArrayList<>();
        isVisited = new boolean[n];
    }

    // 图中常用的能方法
    // 返回结点的个数
    public int getNumOfVertex() {
        return vertexList.size();
    }

    // 返回边的个数
    public int getNumOfEdges() {
        return numOfEdges;
    }

    // 显示图对应的矩阵
    public void showGraph() {
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }
    }

    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    // 添加结点
    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }

    // 添加边
    public void insertEdge(int v1, int v2, int weight) {
        if (v1 >= edges.length || v2 >= edges.length) {
            throw new RuntimeException("该结点标号越界");
        }
        // 考虑无向图
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }

}

4.3 图的深度优先 VS 广度优先