Java数据结构之图

图 - 基础和Overview

数据结构图(Graph)详解

图的概念

图(Graph)是由顶点和连接顶点的边构成的离散结构。在计算机科学中**，图是最灵活的数据结构之一**，很多问题都可以使用图模型进行建模求解。例如：生态环境中不同物种的相互竞争、人与人之间的社交与关系网络、化学上用图区分结构不同但分子式相同的同分异构体、分析计算机网络的拓扑结构确定两台计算机是否可以通信、找到两个城市之间的最短路径等等。

图的基础

定义

图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

图（多对多）和线性表（一对一），树（一对多）的差异：

• 线性表中我们把数据元素叫元素，树中将数据元素叫结点，在图中数据元素，我们则称之为顶点(Vertex)。
• 线性表可以没有元素，称为空表；树中可以没有节点，称为空树；但是，在图中不允许没有顶点(有穷非空性)。
• 线性表中的各元素是线性关系，树中的各元素是层次关系，而图中各顶点的关系是用边来表示(边集可以为空)。

相关术语

• 顶点的度：顶点Vi的度(Degree)是指在图中与Vi相关联的边的条数。对于有向图来说，有**入度(In-degree)和出度(Out-degree)**之分，有向图顶点的度等于该顶点的入度和出度之和。

• 邻接：

  • 若无向图中的两个顶点V1和V2存在一条边(V1,V2)，则称顶点V1和V2邻接(Adjacent)；
  • 若有向图中存在一条边<V3,V2>，则称顶点V3与顶点V2邻接，且是V3邻接到V2；

• 路径：在无向图中，若从顶点Vi出发有一组边可到达顶点Vj，则称顶点Vi到顶点Vj的顶点序列为从顶点Vi到顶点Vj的路径(Path)。

• 连通：若从Vi到Vj有路径可通，则称顶点Vi和顶点Vj是连通(Connected)的。

• 权(Weight)：有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权(Weight)。

  • 由于图存储结构中顶点之间的关系是用线来表示的，因此 (V1,V2) 还可以用来表示无向图中连接 V1 和 V2 的线，又称为边；同样，<V1,V2> 也可用来表示有向图中从 V1 到 V2 带方向的线，又称为弧。

类型

1. 无向图：如果图中任意两个顶点之间的边都是无向边(简而言之就是没有方向的边)，则称该图为无向图(Undirected graphs)。无向图中的边使用小括号“()”表示; 比如 (V1,V2);

2. 有向图：如果图中任意两个顶点之间的边都是有向边(简而言之就是有方向的边)，则称该图为有向图(Directed graphs)。有向图中的边使用尖括号“<>”表示; 比如<V1,V2>；

3. 完全图：

   • 无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。(含有n个顶点的无向完全图有(n×(n-1))/2条边)
   • 有向完全图：在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。(含有n个顶点的有向完全图有n×(n-1)条边)

图的存储结构

邻接矩阵表示法

图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

• 无向图：

  

  二维数组中：0表示两个顶点之间没有边，1表示两个顶点之间有边。对于矩阵的主对角线的值，全为0是因为不存在顶点的边。

• 有向图：

  

  主对角线上数值依然为0。但因为是有向图，所以此矩阵并不对称，比如由v1到v0有弧，得到arc[1][0]=1，而v0到v1没有弧，因此arc[0][1]=0。

邻接矩阵表示法的缺点：由于存在n个顶点的图需要n*n个数组元素进行存储，当图为稀疏图时，使用邻接矩阵存储方法将会出现大量0元素，这会造成极大的空间浪费。这时，可以考虑使用邻接表表示法来存储图中的数据。

邻接表表示法

在之前线性表的学习中提到过，顺序存储结构就存在预先分配内存可能造成存储空间浪费的问题，于是引出了链式存储的结构。同样的，我们也可以考虑对边或弧使用链式存储的方式来避免空间浪费的问题。

邻接表表示法是顺序存储结构+链式存储结构。

邻接表由表头节点和表节点两部分组成，图中每个顶点均对应一个存储在数组中的表头节点。如果这个表头节点所对应的顶点存在邻接节点，则把邻接节点依次存放于表头节点所指向的单向链表中。

• 无向图：

  无向图的邻接表结构：

  

  在上图中，顶点表的各个结点由data和firstedge两个域表示，data是数据域，存储顶点的信息，firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。例如：v1顶点与v0、v2互为邻接点，则在v1的边表中，adjvex分别为v0的0和v2的2。

  PS：对于无向图来说，使用邻接表进行存储也会出现数据冗余的现象。例如上图中，顶点V0所指向的链表中存在一个指向顶点V3的同事，顶点V3所指向的链表中也会存在一个指向V0的顶点。

• 有向图：

  若是有向图，邻接表结构是类似的，但要注意的是有向图由于有方向的。因此，有向图的邻接表分为出边表和入边表(又称逆邻接表)，出边表的表节点存放的是从表头节点出发的有向边所指的尾节点；入边表的表节点存放的则是指向表头节点的某个顶点。

  

• 带权图：

  对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可

  

图的遍历（BFS&DFS）

图的遍历分为深度优先搜索（DFS）和广度优先搜索（BFS）。图的深度优先搜索(Depth First Search)，和树的先序遍历比较类似；广度优先搜索算法(Breadth First Search)，又称为"宽度优先搜索"或"横向优先搜索"，和树的层次遍历比较相似。

深度优先搜索（DFS）

深度优先搜索思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

显然，深度优先搜索是一个递归的过程。

无向图的深度优先搜索

下面以"无向图"为例，来对深度优先搜索进行演示。

对上面的图G1进行深度优先遍历，从顶点A开始：

第1步：访问A。

第2步：访问(A的邻接点)C。 在第1步访问A之后，接下来应该访问的是A的邻接点，即"C,D,F"中的一个。但在本文的实现中，顶点ABCDEFG是按照顺序存储，C在"D和F"的前面，因此，先访问C。

第3步：访问(C的邻接点)B。 在第2步访问C之后，接下来应该访问C的邻接点，即"B和D"中一个(A已经被访问过，就不算在内)。而由于B在D之前，先访问B。

第4步：访问(C的邻接点)D。 在第3步访问了C的邻接点B之后，B没有未被访问的邻接点；因此，返回到访问C的另一个邻接点D。

第5步：访问(A的邻接点)F。 前面已经访问了A，并且访问完了"A的邻接点B的所有邻接点(包括递归的邻接点在内)"；因此，此时返回到访问A的另一个邻接点F。

第6步：访问(F的邻接点)G。

第7步：访问(G的邻接点)E。

因此访问顺序是：A -> C -> B -> D -> F -> G -> E

有向图的深度优先搜索

下面以"有向图"为例，来对深度优先搜索进行演示。

对上面的图G2进行深度优先遍历，从顶点A开始：

第1步：访问A。

第2步：访问B。 在访问了A之后，接下来应该访问的是A的出边的另一个顶点，即顶点B。

第3步：访问C。 在访问了B之后，接下来应该访问的是B的出边的另一个顶点，即顶点C,E,F。在本文实现的图中，顶点ABCDEFG按照顺序存储，因此先访问C。

第4步：访问E。 接下来访问C的出边的另一个顶点，即顶点E。

第5步：访问D。 接下来访问E的出边的另一个顶点，即顶点B,D。顶点B已经被访问过，因此访问顶点D。

第6步：访问F。 接下应该回溯"访问A的出边的另一个顶点F"。

第7步：访问G。

因此访问顺序是：A -> B -> C -> E -> D -> F -> G

广度优先搜索（BFS）

广度优先搜索算法(Breadth First Search)，又称为"宽度优先搜索"或"横向优先搜索"，简称BFS。

广度优先搜索思想：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。

换句话说，广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路径长度为1,2…的顶点。

无向图的广度优先搜索

下面以"无向图"为例，来对广度优先搜索进行演示。还是以上面的图G1为例进行说明。

第1步：访问A。

第2步：依次访问C,D,F。 在访问了A之后，接下来访问A的邻接点。前面已经说过，在本文实现中，顶点ABCDEFG按照顺序存储的，C在"D和F"的前面，因此，先访问C。再访问完C之后，再依次访问D,F。

第3步：依次访问B,G。 在第2步访问完C,D,F之后，再依次访问它们的邻接点。首先访问C的邻接点B，再访问F的邻接点G。

第4步：访问E。 在第3步访问完B,G之后，再依次访问它们的邻接点。只有G有邻接点E，因此访问G的邻接点E。

因此访问顺序是：A -> C -> D -> F -> B -> G -> E

有向图的广度优先搜索

下面以"有向图"为例，来对广度优先搜索进行演示。还是以上面的图G2为例进行说明。

第1步：访问A。

第2步：访问B。

第3步：依次访问C,E,F。 在访问了B之后，接下来访问B的出边的另一个顶点，即C,E,F。前面已经说过，在本文实现中，顶点ABCDEFG按照顺序存储的，因此会先访问C，再依次访问E,F。

第4步：依次访问D,G。 在访问完C,E,F之后，再依次访问它们的出边的另一个顶点。还是按照C,E,F的顺序访问，C的已经全部访问过了，那么就只剩下E,F；先访问E的邻接点D，再访问F的邻接点G。

因此访问顺序是：A -> B -> C -> E -> F -> D -> G

图的实现

图的实现有：

• 邻接矩阵实现的无向图
• 邻接表实现的无向图
• 邻接矩阵实现的有向图
• 邻接表实现的有向图

这里先写一下最简单的邻接矩阵实现的无向图，后面的以后再补。

可以参考相关实现给出的四种代码。

邻接矩阵实现的无向图

邻接矩阵实现的无向图代码如下：

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Scanner;

/**
 * 邻接矩阵实现无向图（Undirected Graph）
 */
public class MatrixUDG {
    private char[] vertices;    // 顶点数组
    private int[][] matrix;     // 边数组（矩阵）

    /**
     * 构造方法
     * 创建图（自己输入数据）
     */
    public MatrixUDG() {
        Scanner scanner = new Scanner(System.in);
        // 输入顶点数和边数
        System.out.print("请输入顶点数：");
        int countV = scanner.nextInt();
        System.out.print("请输入边数：");
        int countE = scanner.nextInt();
        // 初始化顶点
        vertices = new char[countV];
        for (int i = 0; i < countV; i++) {
            System.out.print("请输入第"+i+"个顶点的字符：");
            vertices[i] = scanner.next().charAt(0);
        }
        // 初始化边
        matrix = new int[countV][countV];
        for (int i = 0; i < countE; i++) {
            System.out.print("请输入第"+(i+1)+"条边的起始顶点：");
            char c1 = scanner.next().charAt(0);
            System.out.print("请输入第"+(i+1)+"条边的结束顶点：");
            char c2 = scanner.next().charAt(0);
            int p1 = getPosition(c1);
            int p2 = getPosition(c2);
            if (p1==-1 || p2==-1){  // 防止输入异常
                System.out.println("输入有误！");
                return;
            }
            // 无向图的邻接矩阵表示法
            matrix[p1][p2] = 1;
            matrix[p2][p1] = 1;
        }
    }

    /**
     * 构造方法
     * 创建图（根据）
     * @param vertices
     * @param matrix
     */
    public MatrixUDG(char[] vertices, int[][] matrix) {
        this.vertices = vertices;
        this.matrix = matrix;
    }

    /**
     * 返回顶点v的第一个邻接顶点
     * 失败则返回空格字符' '
     * @param v
     * @return
     */
    public char firstVertex(char v){
        int index = getPosition(v);
        if (index<0 || index > vertices.length - 1){
            return  ' ';
        }
        for (int i = 0; i < vertices.length; i++) {
            if (matrix[index][i] == v){
                return vertices[i];
            }
        }
        return  ' ';
    }

    /**
     * 深度优先搜索遍历图（递归实现）
     */
    public void dfs(){
        // 初始化，所有的顶点都标记为没有访问状态(boolean数组默认是false)
        boolean[] visited = new boolean[vertices.length];   // 顶点访问标记
        System.out.println("深度优先搜索遍历图结果如下：");
        for (int i = 0; i < visited.length; i++) {
            if (!visited[i]){   // 第i个顶点没有被访问
                dfs(i, visited);
            }
        }
        System.out.println();   // 换行
    }
    /**
     * 深度优先搜索遍历图（递归实现）
     * 从第i个顶点开始，一直往下走
     * @param i 指定开始的顶点
     * @param visited 顶点访问标记
     */
    private void dfs(int i, boolean[] visited){
        visited[i] = true;  // 首先将顶点vertices[i]设置为已被访问
        System.out.print(vertices[i]+ " ");    // 输出该顶点（遍历到该顶点了）
        for (int w = firstVertex(i); w != -1; w=nextVertex(i,w)) {
            if (!visited[w]){   // 第w个顶点没有被访问
                dfs(w, visited);
            }
        }
    }

    /**
     * 广度优先搜索遍历图（类似于树的层次遍历）
     * 使用队列实现
     */
    public void bfs(){
        boolean[] visited = new boolean[vertices.length];   // 顶点访问标记
        ArrayDeque<Integer> queue = new ArrayDeque<>(); // 队列，存储顶点在vertices数组中的索引
        System.out.println("广度优先搜索遍历图结果如下：");
        for (int i = 0; i < vertices.length; i++) {
            if (!visited[i]){   // 该顶点没有被遍历
                System.out.print(vertices[i]+" ");  // 输出该顶点（遍历到该顶点了）
                visited[i] = true;
                queue.addLast(i);   // 入队
            }
            while (!queue.isEmpty()){
                int first = queue.removeFirst();    // 出队
                for (int j = firstVertex(first); j != -1; j=nextVertex(first,j)) {
                    if (!visited[j]){
                        System.out.print(vertices[j]+" ");
                        visited[j] = true;
                        queue.addLast(j);   // 入队
                    }
                }
            }
        }
        System.out.println();   // 换行
    }

    /**
     * 打印matrix矩阵
     */
    public void printMatrix(){
        System.out.println();   // 换行
        for (int[] ints ：matrix) {
            System.out.println(Arrays.toString(ints));
        }
    }


    /**
     * 根据指定字符，返回该字符在顶点数组中的下标
     * 私有方法，在构造方法中被使用
     * @param c 指定字符
     * @return 返回改字符在顶点数组中的下标，方便我们创建边数组
     */
    private int getPosition(char c) {
        for (int i = 0; i < vertices.length; i++) {
            if (c==vertices[i]){
                return i;
            }
        }
        return -1;
    }

    /**
     * 返回顶点v的第一个邻接顶点的索引（失败则返回-1）
     * 私有方法，在深度优先搜索中使用
     * @param v 顶点v在顶点数组vertices中的索引
     * @return
     */
    private int firstVertex(int v){
        if (v<0 || v > vertices.length-1){  // 参数v不合法
            return -1;
        }
        for (int i = 0; i < vertices.length; i++) {
            if (matrix[v][i]==1){
                return i;
            }
        }
        return -1;
    }

    /**
     * 返回顶点v相对于w的下一个邻接顶点的索引（失败则返回-1）
     * 也就是说，在顶点数组vertices中，从索引w之后开始遍历！查找出之后顶点v的邻接顶点的索引
     * @param v 顶点v在顶点数组vertices中的索引
     * @param w 所指定的值，合法范围为顶点数组vertices中的索引范围
     * @return
     */
    private int nextVertex(int v, int w){
        if (v<0 || v > vertices.length-1 || w<0 || w > vertices.length-1){  // 参数不合法
            return -1;
        }
        for (int i = w+1; i < vertices.length; i++) {   // 在顶点数组vertices中，从索引w之后开始遍历！
            if (matrix[v][i]==1){
                return i;
            }
        }
        return -1;
    }
}

其中深度优先搜索看起来比较麻烦，其实打下草稿逻辑就能搞懂，或者debug一下。

在dfs中使用到的私有方法firstVertex和nextVertex，光看代码可能不太理解意思，但是画出边数组（矩阵）就很清晰了，特别是为什么会有nextVertex方法。

邻接表实现的无向图

可以参考相关实现给出的四种代码。

邻接矩阵实现的有向图

可以参考相关实现给出的四种代码。

邻接表实现的有向图

可以参考相关实现给出的四种代码。

---

最小生成树(Prim & Kruskal)

相关名词

什么是连通图，（强）连通图详解

什么是生成树，生成树（生成森林）详解

• 连通图：在无向图中，若任意两个顶点vi与vj都有路径相通，则称该无向图为连通图。
• 强连通图：在有向图中，若任意两个顶点vi与vj都有路径相通，则称该有向图为强连通图。
• 连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。
• 生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
• 最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。

对连通图进行遍历，过程中所经过的边和顶点的组合可看做是一棵普通树，通常称为生成树。

如图 1 所示，图 1a) 是一张连通图，图 1b) 是其对应的 2 种生成树。

连通图中，由于任意两顶点之间可能含有多条通路，遍历连通图的方式有多种，往往一张连通图可能有多种不同的生成树与之对应。

连通图中的生成树必须满足以下 2 个条件：

1. 包含连通图中所有的顶点；
2. 任意两顶点之间有且仅有一条通路。

因此，连通图的生成树具有这样的特征，即生成树中边的数量 = 顶点数 - 1。

最小生成树算法

• Kruskal算法是从最小权重边着手，将森林里的树逐渐合并
• prim算法是从顶点出发，在根结点的基础上建起一棵树

Kruskal算法

Kruskal算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。

1. 把图中的所有边按代价从小到大排序；
2. 把图中的n个顶点看成独立的n棵树组成的森林；
3. 按权值从小到大选择边，所选的边连接的两个顶点ui，vi应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
4. 重复(3)，直到所有顶点都在一颗树内或者有n-1条边为止。

Prim算法

Prim算法可以称为“加点法”，**每次迭代选择代价最小的边对应的点，加入到最小生成树中。**算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。

1. 图的所有顶点集合为V；初始令集合u={s}，v=V−u;
2. 在两个集合u，v能够组成的边中，选择一条代价最小的边(u0,v0)，加入到最小生成树中，并把v0并入到集合u中。
3. 重复上述步骤，直到最小生成树有n-1条边或者n个顶点为止。

由于不断向集合u中加点，所以最小代价边必须同步更新；需要建立一个辅助数组closedge,用来维护集合v中每个顶点与集合u中最小代价边信息：

总结：因为Kruskal涉及大量对边的操作，所以它适用于稀疏图；普通的prim算法适用于稠密图，但堆优化的prim算法更适用于稀疏图，因为其时间复杂度是由边的数量决定的。

最短路径(Dijkstra & Frolyd)

图 - 最短路径(Dijkstra & Frolyd)

拓扑排序(Topological sort)

图 - 拓扑排序(Topological sort)

AOE & 关键路径

图 - AOE & 关键路径