数据结构--图

2023-02-09

字数统计: 1.6k字 | 阅读时长≈ 7分

图：（多对多关系，非线性结构）

定义：
- 图G（Graph）由两个集合V（Vertex）和E（Edge）组成，记为G=(V，E)。（图由顶点集和边集组成）
- V是顶点的有限集合，记为V(G)
- E是连接V中两个不同顶点的边的有限集合，记为E(G)
- 图中不能一个顶点也没有，图的顶点集V一定非空，但边集E可以为空，此时图中只有顶点而没有边

有向图：如果表示边的顶点对（或序偶）是有序的，则称G为有向图（边带方向）
无向图：如果代表边的顶点对（或序偶）是无序的，则称G为无向图（边不带方向）
完全图：
- 完全无向图：每两个顶点之间都存在着一条边。含有n个顶点的完全无向图有n(n-1)/2条边
- 完全有向图：每两个顶点之间都存在着方向相反的两条边。含有n个顶点的完全有向图包含有n(n-1)条边。
带权图（网）：边上带有值的图
子图：在原图基础上去掉某些边或顶点
度：该顶点端点边的数目（无向图的全部顶点的度的和等于边数的2倍，有向图的全部顶点的入度之和与出度之和相等，并且等于边数）
- 出度：有向图中该顶点出发指出的边数
- 入度：有向图中指向该顶点的边数
路径：从某个顶点到另一个顶点经过的顶点序列，如（0,3,2,1）
- 路径长度：路径经过边的条数
- 简单路径：除开始点和结束点可以相同外，其余顶点均不相同（中间无经过同一顶点多次）
- 环（回路）：一条路径上开始和结束顶点相同
连通：顶点到顶点有路径可到达
- 连通图：任意两个顶点都连通(任意两个顶点都有路径可达)
- 连通分量：无向图G中的极大连通子图(任何连通图的连通分量只有一个即本身，而非连通图有多个连通分量)
强连通：任意两个顶点都互相可达
- 强连通分量：有向图G中的极大强连通子图（强连通图只有一个强连通分量即本身，非强连通图有多个强连通分量。一般地单个顶点自身就是一个强连通分量）
生成树：包含图中全部顶点的一个极小连通子图（n个顶点，n-1条边）
- 最小生成树：多颗生成树中权值和最小的(如果上图只有这两个生成树，则生成树1的权值和为1 + 2 + 3 =6，生成树2的权值和为1 + 4 + 5 =10，则生成树1为最小生成树)
图的存储结构（实现方式）：
- 邻接矩阵：顶点之间邻接关系的矩阵（用二维数组存储）
  - 无向图邻接矩阵(关于主对角线对称)
  - 有向图邻接矩阵
  - 带权有向图邻接矩阵
- 邻接表
  - 无向图邻接表：
  - 带权有向图邻接表：
    
    weight:权值
图的遍历：
- 深度优先遍历（DFS）：它从图的某个顶点开始遍历，沿着一条路径走到底，直到不能再走为止，然后回溯到前一个节点，继续沿着另一条路径走到底，直到所有的节点都被访问过为止
- 广度优先遍历（BFS）（逐层遍历）：它从图的某个顶点开始遍历，先访问该顶点的所有邻居节点，然后依次访问它们的邻居节点，直到所有的节点都被访问过为止

邻接矩阵实现图

//实现1
public class Graph {
    private int V; // 图的顶点数
    private int[][] adj; // 邻接矩阵表示图
    
    //初始化
    public Graph(int v) {
        V = v;
        adj = new int[v][v];
    }

    // 添加一条边
    public void addEdge(int v, int w) {
        adj[v][w] = 1;
    }

    //删除一条边
    public void removeEdge(int i, int j) {
        adj[i][j] = 0;
        adj[j][i] = 0;
    }

    //显示邻接矩阵
    public void printGraph() {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                System.out.print(adj[i][j] + " ");
            }
            System.out.println();
        }
    }

    // 深度优先搜索
    public void dfs(int v) {
        boolean[] visited = new boolean[V];
        dfsUtil(v, visited);
    }
    private void dfsUtil(int v, boolean[] visited) {
        visited[v] = true;
        System.out.print(v + " ");

        for (int i = 0; i < V; i++) {
            if (adj[v][i] == 1 && !visited[i]) {
                dfsUtil(i, visited);
            }
        }
    }

    // 广度优先搜索
    public void bfs(int s) {
        boolean[] visited = new boolean[V];
        LinkedList<Integer> queue = new LinkedList<>();

        visited[s] = true;
        queue.add(s);

        while (queue.size() != 0) {
            s = queue.poll();
            System.out.print(s + " ");

            for (int i = 0; i < V; i++) {
                if (adj[s][i] == 1 && !visited[i]) {
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }
    }

}

//实现2
public class Graph {

    private ArrayList<String> vertexList; //顶点集
    private int[][] edges; //边集，即邻接矩阵
    
    /**
    * 
    * @param n 矩阵行和列数（一般为顶点个数）
    */
    public Graph(int n) {
        edges = new int[n][n];
        vertexList = new ArrayList<String>(n);
    }

    /**
    * 添加顶点进顶点集
    * @param Vertexs 顶点数组
    */
    public void insertVertex(String Vertexs[]) {
        for(String vertex: Vertexs) {
            vertexList.add(vertex);
        }
    }

    /**
    *添加边进边集（即修改二维数组的值）
    * @param v1 第一个顶点对应的下标
    * @param v2 第二个顶点对应的下标
    * @param weight 顶点之间关系
    *              如 1 ：邻接
    *                 0 ：其他
    */
    public void insertEdge(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
    }

    /**
    显示图对应的矩阵（遍历二维数组）
    **/
    public void showGraph() {
        for(int[] link : edges) {
            System.out.println(Arrays.toString(link));
        }
    }
}

邻接表实现图

public class Graph {
    private int V; // 图的顶点数
    private LinkedList<Integer>[] adj; // 邻接表表示图

    public Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    // 添加一条边
    public void addEdge(int v, int w) {
        adj[v].add(w);
    }

    // 深度优先搜索
    public void dfs(int v) {
        boolean[] visited = new boolean[V];
        dfsUtil(v, visited);
    }
    private void dfsUtil(int v, boolean[] visited) {
        visited[v] = true;
        System.out.print(v + " ");

        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n]) {
                dfsUtil(n, visited);
            }
        }
    }

    // 广度优先搜索
    public void bfs(int s) {
        boolean[] visited = new boolean[V];
        LinkedList<Integer> queue = new LinkedList<>();

        visited[s] = true;
        queue.add(s);

        while (queue.size() != 0) {
            s = queue.poll();
            System.out.print(s + " ");

            Iterator<Integer> i = adj[s].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }

}

本文作者： zzr
本文链接： http://zzruei.github.io/2023/02ead90048.html
版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！