数据结构之图论详解_数据结构 图论

邻接顶点，顾名思义就是相邻相接的顶点，相接也就是有 边 将两者连接起来了，因此就相邻了。

顶点的度：顶点v的度是指与它相关联的边的条数，记作deg(v)。在有向图中，顶点的度等于该顶点的入度与出度之和，其中顶点v的入度是以v为终点的有向边的条数，记作indeV(v)；顶点v的出度是以v为起始点的有向边的条数，记作outdev(v)。因此：dev(v)= indev(v)+ outdev(v)。注意：对于无向图，顶点的度等于该顶点的入度和出度，即dev(v)= indev(v) = outdev(v)。

顶点A的入度：指向A的边数量；顶点A的出度：从A出发指向别的顶点的边数量。

路径：在图G=(V，E)中，若从顶点vi出发有一组边使其可到达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径。

路径长度：对于不带权的图，一条路径的路径长度是指该路径上的边的条数；对于带权的图，一条路径的路径长度是指该路径上各个边权值的总和。

权值就是指该边对应的数值，可能是5，可能是8... 如下所示：

简单路径与回路：若路径上各顶点v1，v2，v3，…，vm均不重复，则称这样的路径为简单路径。若路径上第一个顶点v1和最后一个顶点vm重合，则称这样的路径为回路或环。

子图：设图G = {V, E}和图G1 = {V1，E1}，若V1属于V且E1属于E，则称G1是G的子图。也就是顶点集合是子集并且边的集合也是子集，那整个图就是子图。 

连通图：在无向图中，若从顶点v1到顶点v2有路径，则称顶点v1与顶点v2是连通的。如果图中任意一对顶点都是连通的，则称此图为连通图。

强连通图：在有向图中，若在每一对顶点vi和vj之间都存在一条从vi到vj的路径，也存在一条从vj到 vi的路 径，则称此图是强连通图。

生成树：一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边。  

图的存储结构

存储图，就需要将图中的节点与边全部保存起来。 

图的存储主要有两种，一种是邻接矩阵，另一种是邻接表。

邻接矩阵

节点的存储使用一个数组即可，但是节点之间的边呢？因为节点与节点之间的关系就是连通与否，即为0或者1，因此邻接矩阵(二维数组)即是：先用一个数组将定点保存，然后采用矩阵来表示节点与节点之间的关系。

具体存储： 

注意：

1、无向图的邻接矩阵是对称的，第i行(列)元素之和，就是顶点i的度。有向图的邻接矩阵则不一定是对称的，第i行(列)元素之后就是顶点i的出(入)度。
2、如果边带有权值，并且两个节点之间是连通的，上图中的边的关系就用权值代替，如果两个顶点不通，则使用无穷大代替。

3、用邻接矩阵存储图的优点是能够快速知道两个顶点是否连通，缺陷是如果顶点比较多，边比较少时，矩阵中存储了大量的0成为系数矩阵，比较浪费空间，并且要求两个节点之间的路径不是很好求。

下面我们就来写对应的代码：

前期准备：顶点数组+邻接矩阵+标志是否为有向图

 // 顶点数组 public char[] array; // 矩阵 public int[][] matrix; // 是否是有向图 public boolean isDirected; /** * 构造方法 * @param array 顶点数组 * @param isDirected 是否为有向图 */ public GraphByMatrix(char[] array, boolean isDirected) { this.array = array; this.isDirected = isDirected; initMatrix(array.length); } /** * 初始化矩阵 * @param size 矩阵的大小 */ private void initMatrix(int size) { // 构造矩阵并初始化 matrix = new int[size][size]; for (int i = 0; i < array.length; i++) { for (int j = 0; j < array.length; j++) { matrix[i][j] = Constant.MAX; } } }

定义无穷：

public class Constant { // 表示权值最大值 public final static int MAX = Integer.MAX_VALUE;}

添加顶点间的边：

 /** * 添加图中顶点的边 * 因为边的关系都是记录在邻接矩阵中，因此我们得通过矩阵来修改边边的权重 * 而矩阵中的下标表示的是顶点数组的下标值 * @param v1 起始顶点 * @param v2 结束顶点 * @param weight 边的权重 */ public void addEdge(char v1,char v2,int weight) { // 1、找到顶点对应数组的下标，并在矩阵中找到 int srcIndex = getIndex(v1); int destIndex = getIndex(v2); // 判断上面的顶点下标是否存在 if (srcIndex == -1 || destIndex == -1) { throw new IllegalArgumentException(\"顶点不存在\"); } // 2、找到下标在矩阵中的位置，并修改 matrix[srcIndex][destIndex] = weight; // 3、判断是否为无向图，如果是，还需将修改对称位置的权值 if (!isDirected) { matrix[destIndex][srcIndex] = weight; } } /** * 获取顶点在顶点数组中的下标 * @param v 顶点 * @return 顶点数组的下标 */ private int getIndex(char v) { // 遍历顶点数组即可 // 这里也可以使用Map来存储顶点和下标的对应关系 for (int i = 0; i < array.length; i++) { if (array[i] == v) { return i; } } return -1; }

获取顶点的度：

 /** * 获取顶点的度 * 有向图 = 入度 + 出度 * @param v 顶点 * @return 顶点的度 */ public int getDevOfV(char v){ // 1、先按照无向图来处理：计算当前顶点为起始位置的边的数量 // 先获取顶点的下标 int index = getIndex(v); if (index == -1) { throw new IllegalArgumentException(\"顶点不存在\"); } // 遍历矩阵，统计当前顶点为起始位置的边的数量 int count = 0; for (int i = 0; i < array.length; i++) { if (matrix[index][i] != Constant.MAX) { count++; } } // 2、如果是有向图，则还需统计入度的数量 if (isDirected) { for (int i = 0; i < array.length; i++) { if (matrix[i][index] != Constant.MAX) {  count++; } } } return count; }

打印图：打印邻接矩阵

 /** * 打印图（打印邻接矩阵） */ public void printGraph() { // 先打印行表头 System.out.printf(\"%c\\t\", \'#\'); for (int i = 0; i < array.length; i++) { System.out.printf(\"%c\\t\", array[i]); } System.out.println(); // 再打印矩阵 for (int i = 0; i < matrix.length; i++) { System.out.printf(\"%c\\t\", array[i]); // 打印列表头 for (int j = 0; j < matrix[i].length; j++) { if (matrix[i][j] != Constant.MAX) {  System.out.printf(\"%d\\t\", matrix[i][j]); } else {  // weight为最大值时，打印∞  System.out.printf(\"%c\\t\", \'∞\'); } } System.out.println(); } }

测试代码：

 public static void main(String[] args) { // 创建图 char[] array = {\'A\',\'B\',\'C\',\'D\'}; GraphByMatrix graph = new GraphByMatrix(array, false); graph.addEdge(\'A\',\'B\',1); graph.addEdge(\'A\',\'D\',1); graph.addEdge(\'B\',\'A\',1); graph.addEdge(\'B\',\'C\',1); graph.addEdge(\'C\',\'B\',1); graph.addEdge(\'C\',\'D\',1); graph.addEdge(\'D\',\'A\',1); graph.addEdge(\'D\',\'C\',1); graph.printGraph(); System.out.println(graph.getDevOfV(\'A\')); }

运行截图：

邻接表

邻接表：使用数组表示顶点的集合，使用链表 表示边的关系。其实这就是仿照哈希表的形式来存储的。用一个数组来顶点，再用一个节点数组来存储顶点数组对应下标的边（使用链表）。

1、无向图邻接表存储：

2、有向图邻接表存储 ：

上面的表示形式是比较复杂的，我们在写代码的时候是不采取这样的方式。

我们是使用 一个数组来存储顶点，另一个数组来存储对应顶点所指向的别的顶点的边，这里的边是一个链表。

前期准备：顶点数组 + 对应顶点的边的数组 +  链表节点

 // 定义节点 static class Node { int src; // 起点 int dest; // 终点 int weight; // 权重 Node next; // 指向下一个邻接点 /** * 构造方法 * @param src 起始位置 * @param dest 结束位置 * @param weight 权重 */ public Node(int src, int dest, int weight) { this.src = src; this.dest = dest; this.weight = weight; } } public char[] array; // 顶点数组 public Node[] nodes; // 存放节点的数组 --> 邻接表 public boolean isDirected; // 是否是有向图 /** * 构造方法 * @param array 顶点数组 */ public GraphByNode(char[] array, boolean isDirected) { this.array = array; this.isDirected = isDirected; // 如果不初始化，nodes为null，无法访问 nodes = new Node[array.length]; }

添加顶点间的边：采取尾插法

 /** * 添加图中顶点的边 * 顶点数组中记录的顶点，但是最终添加的是在节点数组中 * 先得找到节点数组中的对应的下标才行 * @param v1 起始顶点 * @param v2 结束顶点 * @param weight 边的权重 */ public void addEdge(char v1,char v2,int weight) { // 1、找到顶点在节点数组对应的下标 int srcIndex = getIndex(v1); int destIndex = getIndex(v2); if (srcIndex == -1 || destIndex == -1) { throw new IllegalArgumentException(\"顶点不存在！\"); } // 2、遍历边所在的链表判断是否存在该边 Node cur = nodes[srcIndex]; Node prev = null; // 记录前一个节点，用于最后的添加 while (cur != null) { if (cur.src == getIndex(v1) && cur.dest == getIndex(v2)) { return; } prev = cur; cur = cur.next; } // 说明不存在该边，则添加 // 3、将节点添加到节点数组中 Node newNode = new Node(srcIndex, destIndex, weight); // 可能prev为null，说明该节点是第一个节点 if (prev == null) { nodes[srcIndex] = newNode; } else { prev.next = newNode; } // 上面只是把有向图的情况处理完了，但是当是无向图的时候，还需要把反向的边也添加上 if (!isDirected) { // 首先也得判断是否存在于节点数组中 cur = nodes[destIndex]; prev = null; // 记录前一个节点，用于最后的添加 while (cur != null) { if (cur.src == getIndex(v2) && cur.dest == getIndex(v1)) {  return; } prev = cur; cur = cur.next; } // 说明不存在该边，则添加 newNode = new Node(destIndex, srcIndex, weight); // 可能prev为null，说明该节点是第一个节点 if (prev == null) { nodes[destIndex] = newNode; } else { prev.next = newNode; } } } /** * 获取顶点在顶点数组对应的下标 * @param v1 顶点 * @return 顶点在顶点数组对应的下标 */ private int getIndex(char v1) { // 遍历顶点数组找到对应的下标 for (int i = 0; i < array.length; i++) { if (array[i] == v1) { return i; } } return -1; }

 获取顶点的度：

 /** * 获取顶点的度 * 有向图 = 入度 + 出度 * @param v 顶点 * @return 顶点的度 */ public int getDevOfV(char v){ // 先是当作无向图处理 // 1、找到顶点在顶点数组对应的下标 int index = getIndex(v); if (index == -1) { throw new IllegalArgumentException(\"顶点不存在！\"); } // 2、遍历边所在的数组，统计出度 Node cur = nodes[index]; int count = 0; while (cur != null) { count++; cur = cur.next; } // 3、判断是否有向图 if (isDirected) { // 统计入度 // 遍历节点数组，找到所有dest为index的节点，并统计 for (int i = 0; i < array.length; i++) { if (i == index) { // 跳过自己  continue; } else {  cur = nodes[i];  while (cur != null) { if (cur.dest == index) { count++; } cur = cur.next;  } } } } return count; }

打印图：

 /** * 打印图（打印邻接表） */ public void printGraph() { for (int i = 0; i %c\\t\", array[cur.src], array[cur.dest]); cur = cur.next; } System.out.println(); } }

测试代码：

 public static void main(String[] args) { char[] array = {\'A\', \'B\', \'C\', \'D\'}; GraphByNode graph = new GraphByNode(array, true); graph.addEdge(\'A\', \'B\', 1); graph.addEdge(\'A\', \'D\', 1); graph.addEdge(\'B\', \'A\', 1); graph.addEdge(\'B\', \'C\', 1); graph.addEdge(\'C\', \'B\', 1); graph.addEdge(\'C\', \'D\', 1); graph.addEdge(\'D\', \'A\', 1); graph.addEdge(\'D\', \'C\', 1); System.out.println(graph.getDevOfV(\'A\')); graph.printGraph(); }

 运行截图：

图的遍历

图的遍历方式有两种，一种是广度优先遍历，另一种是深度优先遍历。

广度优先遍历（BFS）

广度优先遍历，从起始顶点开始访问，接着访问起始顶点的所有邻接顶点，然后再依次访问这些邻接顶点的邻接顶点，一层一层地向外扩展，直到遍历完整个图。

广度优先遍历与我们在二叉树中学习的 层序遍历 类似，都是先访问完本层，再去访问下一层。因此广度优先遍历也需要用到队列。下图是广度优先遍历的详细描述：

代码实现：

邻接矩阵版：

 /** * 广度优先遍历 * “层序遍历”：队列+标记数组 * @param v 起始顶点 */ public void bfs(char v) { // 申请一个队列 Queue queue = new LinkedList(); // 标记数组：记录是否已经访问过 boolean[] visited = new boolean[array.length]; queue.offer(v); visited[getIndex(v)] = true; // 标记为已访问 while (!queue.isEmpty()) { // 队列不为空 // 取出当前元素 char cur = queue.poll(); System.out.printf(\"%c\\t\", cur); // 打印当前顶点 // 将 当前元素的相邻顶点 全部入队 ——> 遍历邻接矩阵 int index = getIndex(cur); for (int i = 0; i < matrix[index].length; i++) { // 找到相邻顶点，且未访问过 if (matrix[index][i] != Constant.MAX && !visited[i]) {  queue.offer(array[i]); // 列下标对应的是相邻顶点  visited[i] = true; // 标记为已访问 } } } System.out.println(); }

注意：这里不能是打印某个顶点之后再将其在visited数组中置为true，这样会导致多打印。

邻接表版：

 /** * 广度优先遍历 * “层序遍历”：队列+标记数组 * @param v 起始顶点 */ public void bfs(char v) { // 申请一个队列 Queue queue = new LinkedList(); // 标记数组：记录是否已经访问过 boolean[] visited = new boolean[array.length]; queue.offer(v); visited[getIndex(v)] = true; // 标记为已访问 while (!queue.isEmpty()) { char cur = queue.poll(); System.out.printf(\"%c\\t\", cur); // 遍历邻接表：找到对应的链表，遍历 Node node = nodes[getIndex(cur)]; while (node != null) { // 拿到对应顶点下标，判断是否已经访问过 int dest = node.dest; if (!visited[dest]) { // 未访问过，就将对应的顶点入队  queue.offer(array[dest]);  visited[dest] = true; // 标记为已访问 } node = node.next; } } System.out.println(); }

注意：邻接表版 与 邻接矩阵版，只是在存储图的方式上不同，因此也只是在拿数据的方式不同，至于遍历的思路以及处理方式都是一模一样的。 

深度优先遍历（DFS） 

广度优先遍历，从起始顶点开始，沿着一条路径尽可能深地访问节点，直到无法继续（到达已经访问过所有邻接节点），然后回溯到上一个未完全探索的节点，继续沿着另一条路径深入，直到遍历完整个图。

深度优先遍历与我们在二叉树中学习的 前序遍历 类似，都是先尽可能的往深处访问，直至访问不了了，再会返回，从另外一条路访问。前序遍历 用到了 递归的方法，因此这里的深度优先遍历也是需要用到 递归的。下图是深度优先遍历的详细描述： 

代码实现：

邻接矩阵版：

 /** * 深度优先遍历 * “递归”：标记数组 * @param v 起始顶点 */ public void dfs(char v) { // 标记数组：记录是否已经访问过 boolean[] visited = new boolean[array.length]; // 递归方法 dfs(v,visited); System.out.println(); } /** * 深度优先遍历的递归方法 * 打印v并且将visited数组标记为true * @param v 顶点 * @param visited 标记数组 */ private void dfs(char v, boolean[] visited) { // 先打印当前顶点 System.out.printf(\"%c\\t\", v); // 标记为已访问 int index = getIndex(v); visited[index] = true; // 遍历邻接矩阵 for (int i = 0; i < matrix[index].length; i++) { // 找到相邻顶点，且未访问过 if (matrix[index][i] != Constant.MAX && !visited[i]) { // 递归调用 dfs(array[i], visited); } } }

邻接表版： 

 /** * 深度优先遍历 * “递归”：标记数组 * @param v 起始顶点 */ public void dfs(char v) { // 标记数组：记录是否已经访问过 boolean[] visited = new boolean[array.length]; // 递归方法 dfs(v,visited); System.out.println(); } /** * 深度优先遍历的递归方法 * 打印v并且将visited数组标记为true * @param v 顶点 * @param visited 标记数组 */ private void dfs(char v, boolean[] visited) { // 先打印当前顶点 System.out.printf(\"%c\\t\", v); // 标记为已访问 int index = getIndex(v); visited[index] = true; // 遍历邻接表：找到对应的链表，遍历 Node node = nodes[index]; while (node != null) { int dest = node.dest; if (!visited[dest]) { dfs(array[dest], visited); } node = node.next; } }

注意：上述的两种遍历方式的结果并不唯一。有很多因素影响，但最主要还是起始顶点、存储方式、图的类型。

最小生成树

连通图中的每一棵生成树，都是原图的一个极大无环子图，即：从其中删去任何一条边，生成树 就不再连通；反之，再其中引入任何一条新边，都会形成一条回路。 若连通图由n个顶点组成，则其生成树必含n个顶点和n-1条边。

因此构造最小生成树的准则有三条：

1、只能使用图中的边来构造最小生成树。

2、只能使用恰好n-1条边来连接图中的n个顶点。

3、选用的n-1条边不能构成回路。

构造最小生成树的方法：Kruskal算法和Prim算法。这两个算法都采用了逐步求解的贪心策略。 贪心算法：是指在问题求解时，总是做出当前看起来最好的选择。也就是说贪心算法做出的不是整体 最优的的选择，而是某种意义上的局部最优解。贪心算法不是对所有的问题都能得到整体最优解。

Kruskal算法（克鲁斯卡尔算法）

Kruskal算法采取的是全局贪心的策略，即从图中的所有边中取出权值最小的 n-1 条边构成最小生成树。

从图中取出权值最最小的边，意味着需要遍历所有的边去比较求出最小值，但这也太麻烦了，还好优先级队列提供了天然的保障，可以让我们在全局的边中取出最小的。除此之外，还需要 n-1 条边不能构成环，那这怎么判断呢？可以使用一个集合来记录已知的最小生成树中的顶点数量，当符合最小权值边所在的两个顶点属于同一个集合时，就不能添加到最小生成树中，因为同一个集合中的两个顶点所组成的边可能会构成回路（闭环）。因此每当添加一个边之后，两个顶点都需要构成一个新的集合，可能在处理的过程中，会有多个集合，在最终只有一个集合。这里也就是需要用到并查集了。但是这里只需要并查集的 合并成一个集合、查询是否在同一个集合的两个功能。

实现并查集：

/** * UnionFindSet:并查集 */public class UnionFindSet { // 并查集数组 private int[] elem; // 构造方法 public UnionFindSet(int n) { elem = new int[n]; // 将所有的元素放到一个属于自己的集合中 Arrays.fill(elem, -1); } // 实现两个方法： // 1、判断两个顶点是否在一个集合当中 // 2、将两个顶点和并到一个集合中去 /** * 判断两个两个顶点是否在同一个集合中 * @return 属于一个集合，true；反之，则是false */ public boolean isSameSet(int x, int y) { // 先判断下标是否合法 if (x < 0 || y = 0) { x = elem[x]; } return x; // 这里返回的是下标，而不是值 } /** * 将两个顶点合并到一个集合中 * @param x 顶点1 * @param y 顶点2 */ public void union(int x, int y) { // 可能这两个顶点不是孤家寡人，而是有靠山的 // 我们需要将靠山也合并（根结点需合并） int x_root = getRoot(x); int y_root = getRoot(y); // 如果两者已经是同一个集合，则无需合并了 if (x_root == y_root) { return; } // 不能随便和并，为了让查询更加方便，我们得使树尽量平衡 if (x_root > y_root) { // 说明y所在树更高，将x作为叶子 elem[y_root] += elem[x_root]; elem[x_root] = y_root; } else { // 说明x所在的树更高，将x作为叶子 elem[x_root] += elem[y_root]; elem[y_root] = x_root; } }}

关于上述并查集的知识，如果不知道或者忘记的小伙伴，可以去看下面这篇文章：并查集的相关知识 

下面我们就来如何实现Kruskal算法。 

思路：先在所有可用的边中选择一个最小权值的边，再判断这个边是否会构成回路（这个边的两个顶点是否在同一个集合中），如果不会构成回路就添加到最小生成树中，一直重复上述步骤，直至最小生成树构造完成（遍历n-1次）或者图中的边全部使用完了，但是还没有构造完成（这种情况属于该图不是完全连通图）。

问题1：怎么每次都找到权值最小的边呢？

答：使用优先级队列即可。

问题2：优先级队列记录啥呢？

答：记录边呀！将边的信息全部记录，包括：起始位置、结束位置、边的权值。这就需要一个新的类来表示边了。

代码实现：

邻接矩阵版：

 // 定义一条边 static class Edge { public int src; public int dest; public int weight; public Edge(int src, int dest, int weight) { this.src = src; this.dest = dest; this.weight = weight; } } /** * 最小生成树：Kruskal算法 * @param minTree 最小生成树 * @return 最小生成树的权重和 */ public int kruskal(GraphByMatrix minTree) { // 申请一个优先级队列：队列中存储的是边（起始顶点，结束顶点，权值） // 由于我们是需要找权值最小，即小根堆，但由于是自定义类 // 因此得Edge类实现Comparable 或者传入比较器(可以使用lambda表达式) PriorityQueue minQ = new PriorityQueue(new Comparator() { @Override public int compare(Edge o1, Edge o2) { return o1.weight - o2.weight; // 根据权值来排序 } }); // 遍历邻接矩阵将边全部存储到优先级队列中 int n = array.length; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // 注意：无向图的边只需要记录一半即可（实际物理图中只有一半） if (i < j && matrix[i][j] != Constant.MAX) {  minQ.offer(new Edge(i, j, matrix[i][j])); } } } // 开始构造最小生成树 int total = 0; // 记录最小生成树的权重 int size = 0; // 记录最小生成树已经存储的边的个数 UnionFindSet ufs = new UnionFindSet(n); // 并查集：防止最小生成 成环 while (size < n-1 && !minQ.isEmpty()) { // 可能该图不是连通图，得考虑这种情况 // 拿到 当前全局 权值最小的边 Edge e = minQ.poll(); int src = e.src; int dest = e.dest; int weight = e.weight; // 判断是否在并查集中（是否会构成回路） if (!ufs.isSameSet(src, dest)) { // 添加到最小生成树中 // 可以打印出边来观察结果 System.out.println(\"起点: \"+array[src]+\"终点: \"  +array[dest]+\"权值: \"+weight); minTree.addEdge(array[src], array[dest], weight); total += weight; size++; // 边的个数++ } // 将两者记录到并查集中 ufs.union(src, dest); } return size == n-1 ? total : -1; }

测试代码：

 /** * 测试 Kruskal算法的代码 是否实现正确 */ public static void testGraphMinTreeKruskal() { String str = \"abcdefghi\"; char[] array =str.toCharArray(); GraphByMatrix g = new GraphByMatrix(array,false); g.addEdge(\'a\', \'b\', 4); g.addEdge(\'a\', \'h\', 8); g.addEdge(\'b\', \'c\', 8); g.addEdge(\'b\', \'h\', 11); g.addEdge(\'c\', \'i\', 2); g.addEdge(\'c\', \'f\', 4); g.addEdge(\'c\', \'d\', 7); g.addEdge(\'d\', \'f\', 14); g.addEdge(\'d\', \'e\', 9); g.addEdge(\'e\', \'f\', 10); g.addEdge(\'f\', \'g\', 2); g.addEdge(\'g\', \'h\', 1); g.addEdge(\'g\', \'i\', 6); g.addEdge(\'h\', \'i\', 7); GraphByMatrix kminTree = new GraphByMatrix(array,false); System.out.println(g.kruskal(kminTree)); kminTree.printGraph(); }

邻接表版：

 // 定义一条边 static class Edge { public int src; public int dest; public int weight; public Edge(int src, int dest, int weight) { this.src = src; this.dest = dest; this.weight = weight; } } /** * 最小生成树：KruskaL算法 * @param minTree 最小生成树 * @return 最小生成树的权重和 */ public int kruskal(GraphByNode minTree) { // 申请一个优先级队列 // 这里使用lambda表达式: () -> {} // () -> 这是参数, {} -> 这是函数体(因为这里只有) PriorityQueue minQ = new PriorityQueue((o1, o2) -> { return o1.weight-o2.weight; }); // 遍历邻接表，将边全部填充到优先级队列中 int n = array.length; for (int i = 0; i B Edge e2 = new Edge(cur.dest, cur.src, cur.weight); // B->A // 先看看上述边是否在队列中存在了 if (!minQ.contains(e1) && !minQ.contains(e2)) {  minQ.offer(e1); } cur = cur.next; } } // 开始构造最小生成树 UnionFindSet ufs = new UnionFindSet(n); int size = 0; int total = 0; while (size < n-1 && !minQ.isEmpty()) { // 拿到 当前全局 最小的边 Edge e = minQ.poll(); int src = e.src; int dest = e.dest; int weight = e.weight; // 当两个顶点不在一个集合中，才能组成最小生成树 if (!ufs.isSameSet(src, dest)) { minTree.addEdge(array[src], array[dest], weight); size++; total += weight; } ufs.union(src, dest); } return size == n-1 ? total : -1; }

测试代码： 

 /** * 测试 Kruskal算法的代码 是否实现正确 */ public static void testGraphMinTreeKruskal() { String str = \"abcdefghi\"; char[] array =str.toCharArray(); GraphByNode g = new GraphByNode(array,false); g.addEdge(\'a\', \'b\', 4); g.addEdge(\'a\', \'h\', 8); g.addEdge(\'b\', \'c\', 8); g.addEdge(\'b\', \'h\', 11); g.addEdge(\'c\', \'i\', 2); g.addEdge(\'c\', \'f\', 4); g.addEdge(\'c\', \'d\', 7); g.addEdge(\'d\', \'f\', 14); g.addEdge(\'d\', \'e\', 9); g.addEdge(\'e\', \'f\', 10); g.addEdge(\'f\', \'g\', 2); g.addEdge(\'g\', \'h\', 1); g.addEdge(\'g\', \'i\', 6); g.addEdge(\'h\', \'i\', 7); GraphByNode kminTree = new GraphByNode(array,false); System.out.println(g.kruskal(kminTree)); kminTree.printGraph(); }

运行结果：

邻接矩阵版：

邻接表版：

Prim算法（普利姆算法）

与Kruskal算法不同，Prim算法采取的是局部贪心的策略。

Prim算法是将图中的顶点分为两部分，一部分是已经处理的，一部分是待处理的，然后在已处理的顶点与未处理的顶点相连的边全部加入到优先级队列中，找出权值最小的边，添加到最小生成树中。接着再更新集合、最小生成树的参数、优先级队列即可。

代码实现：

邻接矩阵版：

 /** * 最小生成树：Prim算法 * @param minTree 最小生成树 * @param chV 起始顶点 * @return 最小生成树的权重和 */ public int prim(GraphByMatrix minTree,char chV) { // 申请一个优先级队列来存放边 PriorityQueue minQ = new PriorityQueue((o1, o2)->{ return o1.weight-o2.weight; }); int n = array.length; // 将处理的顶点分为一组 Set setX = new HashSet(); // 将未处理的顶点分为一组 Set setY = new HashSet(); // 初始化集合 setX.add(chV); for (int i = 0; i < n; i++) { if (array[i] != chV) { setY.add(array[i]); } } // 将与已处理集合中的顶点相关的边添加到优先级队列中 int index = getIndex(chV); for (int i = 0; i < matrix[index].length; i++) { if (matrix[index][i] != Constant.MAX) { minQ.offer(new Edge(index, i, matrix[index][i])); } } // 开始循环处理 int total = 0; int size = 0; while (size \"+destV+\": \"+weight); total += weight; size++; // 集合更新 setX.add(destV); setY.remove(destV); // 优先级队列更新 index = getIndex(destV); for (int i = 0; i b被使用过，b->a就不行)  if (matrix[index][i] != Constant.MAX && !setX.contains(array[i])) { minQ.offer(new Edge(index, i, matrix[index][i]));  } } } } return size == n-1 ? total : -1; }

测试代码：

 /** * 测试 Prim 算法的代码 是否实现正确 */ public static void testGraphMinTreePrime() { String str = \"abcdefghi\"; char[] array = str.toCharArray(); GraphByMatrix g = new GraphByMatrix(array, false); g.addEdge(\'a\', \'b\', 4); g.addEdge(\'a\', \'h\', 8); g.addEdge(\'b\', \'c\', 8); g.addEdge(\'b\', \'h\', 11); g.addEdge(\'c\', \'i\', 2); g.addEdge(\'c\', \'f\', 4); g.addEdge(\'c\', \'d\', 7); g.addEdge(\'d\', \'f\', 14); g.addEdge(\'d\', \'e\', 9); g.addEdge(\'e\', \'f\', 10); g.addEdge(\'f\', \'g\', 2); g.addEdge(\'g\', \'h\', 1); g.addEdge(\'g\', \'i\', 6); g.addEdge(\'h\', \'i\', 7); GraphByMatrix primTree = new GraphByMatrix(array, false); System.out.println(g.prim(primTree, \'a\')); primTree.printGraph(); }

邻接表版：

 /** * 最小生成树：Prim算法 * @param minTree 最小生成树 * @param chV 起始顶点 * @return 最小生成树的权重和 */ public int prim(GraphByNode minTree,char chV) { // 申请一个优先级队列 PriorityQueue minQ = new PriorityQueue((o1, o2)->{ return o1.weight- o2.weight; }); // 申请两个集合： // setX，存放已经处理的顶点 // setY，存放待处理的顶点 Set setX = new HashSet(); Set setY = new HashSet(); // 初始化集合 setX.add(chV); for (char x : array) { if (x != chV) { setY.add(x); } } // 初始化队列 Node cur = nodes[getIndex(chV)]; while (cur != null) { minQ.offer(new Edge(cur.src, cur.dest, cur.weight)); cur = cur.next; } int total = 0; int size = 0; int n = array.length; while (size < n-1 && !minQ.isEmpty()) { // 拿到最小权值的边 Edge e = minQ.poll(); char srcV = array[e.src]; char destV = array[e.dest]; int weight = e.weight; // 判断这个边的结束位置不是在setX中 if (!setX.contains(destV)) { // 构造最小生成树，更新最小生成树的边数、权值和 minTree.addEdge(srcV, destV, weight); total += weight; size++; // 更新集合 setX.add(destV); setY.remove(destV); // 更新优先级队列 cur = nodes[e.dest]; while (cur != null) {  // 结束位置不能是在setX中  if (!setX.contains(array[cur.dest])) { minQ.offer(new Edge(cur.src, cur.dest, cur.weight));  }  cur = cur.next; } } } return size == n-1 ? total : -1; }

测试代码：

 /** * 测试 Prim 算法的代码 是否实现正确 */ public static void testGraphMinTreePrime() { String str = \"abcdefghi\"; char[] array = str.toCharArray(); GraphByNode g = new GraphByNode(array, false); g.addEdge(\'a\', \'b\', 4); g.addEdge(\'a\', \'h\', 8); //g.addEdge(\'a\', \'h\', 9); g.addEdge(\'b\', \'c\', 8); g.addEdge(\'b\', \'h\', 11); g.addEdge(\'c\', \'i\', 2); g.addEdge(\'c\', \'f\', 4); g.addEdge(\'c\', \'d\', 7); g.addEdge(\'d\', \'f\', 14); g.addEdge(\'d\', \'e\', 9); g.addEdge(\'e\', \'f\', 10); g.addEdge(\'f\', \'g\', 2); g.addEdge(\'g\', \'h\', 1); g.addEdge(\'g\', \'i\', 6); g.addEdge(\'h\', \'i\', 7); GraphByNode primTree = new GraphByNode(array, false); System.out.println(g.prim(primTree, \'a\')); primTree.printGraph(); }

运行结果：

邻接矩阵版：

邻接表版：

最短路径

最短路径问题：从在带权图的某一顶点出发，找出一条通往另一顶点的最短路径，最短也就是沿路径各边的权值总和达到最小。

最短路径分为两种：一种是单源最短路径，另一种是多源最短路径。顾名思义，单源就是指从一个顶点出发到别的顶点的最小值，而多源就是任意取一个顶点求出到其他顶点的最小值。

单源最短路径中比较经典的算法是，迪杰斯特拉算法 与 贝尔曼-福特算法。

单源最短路径问题：给定一个图G = (V，E) ，求源结点s ∈ V 到图中每个结点v ∈ V的最短路径。

单源最短路径 — Dijkstra算法

Dijkstra算法就适用于解决带权重的有向图上的单源最短路径问题，同时算法要求图中所有边的权重非负。一般在求解最短路径的时候都是已知一个起点和一个终点，所以使用Dijkstra算法求解过后也就得到了所需起点到终点的最短路径。 针对一个带权有向图G，将所有结点分为两组S和Q，S是已经确定最短路径的结点集合，在初始时为空（初始时也可以将源节点s放入，毕竟源节点到自己的代价是0），Q 为其余未确定最短路径的结点集合，每次从Q 中找出一个起点到该结点代价最小的结点u ，将u 从Q 中移出，并放入S 中，对u的每一个相邻结点v进行松弛操作。松弛即对每一个相邻结点v ，判断源节点s到结点u 的代价与u 到v 的代价之和是否比原来s 到v 的代价更小，若代价比原来小则要将s 到v 的代价更新为s 到u 与u 到v 的代价之和，否则维持原样。如此一直循 环直至集合Q为空，即所有节点都已经查找过一遍并确定了最短路径，至于一些起点到达不了的结点在算法循环后其代价仍为初始设定的值，不发生变化。Dijkstra算法每次都是选择V-S中最小的路径节点来进行更新，并加入S中，所以该算法使用的是贪心策略。 Dijkstra算法存在的问题是不支持图中带负权路径，如果带有负权路径，则可能会找不到一些路径的最短路径。

代码实现：

邻接矩阵版：

 /** * 迪杰斯特拉算法 * @param vSrc 起始顶点 * @param dist 距离数组 * @param pPath 路径序列数组 */ public void dijkstra(char vSrc,int[] dist,int[] pPath) { // 前期准备：初始化距离数组、路径序列数组、是否确认最短路径数组 int src = getIndex(vSrc); Arrays.fill(dist, Constant.MAX); dist[src] = 0; Arrays.fill(pPath, -1); int n = array.length; boolean[] isShortPath = new boolean[n]; // 核心：每次只能确定一个最短路径 // 需要遍历n次，因为每次只是确定1个（第一个是需要手动更新的） for (int k = 0; k < n; k++) { // 从距离数组中找到基准元素并且将最短路径给找到 int min = Constant.MAX; // 记录(此次)当前距离数组的最小值 int u = 0; // 记录最小值的下标(初始化为啥值都是可以的) for (int i = 0; i < n; i++) { // 未确定为最短路径 且 起始点到该点的距离小于min（最小值） if (!isShortPath[i] && dist[i] < min) {  min = dist[i];  u = i; } } isShortPath[u] = true; // 最小值确定了，对应的位置设置为true // 以 基准元素 去遍历相邻边，看看是否小于 距离数组对应的值 // 这其实就是 换条路 看看是否 小于 前面的那条路 for (int i = 0; i < matrix[u].length; i++) { if (!isShortPath[i] && matrix[u][i] != Constant.MAX && dist[u]+matrix[u][i]  更新这条路  dist[i] = dist[u]+matrix[u][i];  // 记录路径序列(当前路径的上一级是谁 --> 与并查集的方式一样)  pPath[i] = u; } } } } /** * 打印 dijkstra算法 所计算出来的最短路径序列 * @param vSrc 起始顶点 * @param dist 距离数组 * @param pPath 路径序列数组 */ public void printShortPath(char vSrc,int[] dist,int[] pPath) { int n = array.length; int src = getIndex(vSrc); // 遍历 路径序列数组，打印出序列 for (int i = 0; i < n; i++) { // 当遇到起始顶点时，跳过 if (i == src) { continue; } // 将 路径序列记录下来 Stack stack = new Stack(); int temp = i; while (pPath[temp] != -1) { stack.push(temp); temp = pPath[temp]; } // 打印 路径序列 // 先打印起始顶点 System.out.printf(\"%c->\",array[src]); // 打印后续顶点 while (!stack.isEmpty()) { System.out.printf(\"%c->\", array[stack.pop()]); } // 打印最短路径值 System.out.println(dist[i]); } }

测试代码：

 /** * 测试 迪杰斯特拉 算法的代码 是否实现正确 */ public static void testGraphDijkstra() { String str = \"syztx\"; char[] array = str.toCharArray(); GraphByMatrix g = new GraphByMatrix(array,true); g.addEdge(\'s\', \'t\', 10); g.addEdge(\'s\', \'y\', 5); g.addEdge(\'y\', \'t\', 3); g.addEdge(\'y\', \'x\', 9); g.addEdge(\'y\', \'z\', 2); g.addEdge(\'z\', \'s\', 7); g.addEdge(\'z\', \'x\', 6); g.addEdge(\'t\', \'y\', 2); g.addEdge(\'t\', \'x\', 1); g.addEdge(\'x\', \'z\', 4); int[] dist = new int[array.length]; int[] parentPath = new int[array.length]; g.dijkstra(\'s\', dist, parentPath); System.out.println(\"此处可设置端点来调试，观察前面的算法是否正确\"); g.printShortPath(\'s\', dist, parentPath); }

运行结果：

邻接表版：

 /** * 迪杰斯特拉算法 * @param vSrc 起始顶点 * @param dist 距离数组 * @param pPath 路径序列数组 */ public void dijkstra(char vSrc,int[] dist,int[] pPath) { // 前期准备：初始化距离数组、路径序列数组、确认是否为最短路径数组 int src = getIndex(vSrc); Arrays.fill(dist, Constant.MAX); dist[src] = 0; Arrays.fill(pPath, -1); int n = array.length; boolean[] isShortPath = new boolean[n]; // 核心：依旧是遍历n次 for (int k = 0; k < n; k++) { int min = Constant.MAX; int u = 0; // 找到基准元素（遍历距离数组找到最小值） for (int i = 0; i < n; i++) { if (!isShortPath[i] && dist[i] < min) {  min = dist[i];  u = i; } } isShortPath[u] = true; // 看看是 通过 基准顶点找到的路径 是否 小于 其他边的路径 Node cur = nodes[u]; while (cur != null) { // 拿到 终点 与 权值 int v = cur.dest; int weight = cur.weight; // 未确定最短路径 并且 该路径确实是少的 // 邻接表中不存在 未连接 的边 if (!isShortPath[v] && dist[u]+weight < dist[v]) {  // 更新路径+路径序列  dist[v] = dist[u]+weight;  pPath[v] = u; } cur = cur.next; } } } /** * 打印 dijkstra算法 所计算出来的最短路径序列 * @param vSrc 起始顶点 * @param dist 距离数组 * @param pPath 路径序列数组 */ public void printShortPath(char vSrc,int[] dist,int[] pPath) { int n = array.length; int src = getIndex(vSrc); // 遍历 路径序列数组 for (int i = 0; i < n; i++) { // 遍历到起始顶点时，直接跳过 if (i == src) { continue; } Stack stack = new Stack(); int temp = i; while (pPath[temp] != -1) { stack.push(temp); temp = pPath[temp]; } // 打印 路径序列 // 先打印起始顶点 System.out.printf(\"%c->\",array[src]); // 打印后续顶点 while (!stack.isEmpty()) { System.out.printf(\"%c->\", array[stack.pop()]); } // 打印最短路径值 System.out.println(dist[i]); } }

 测试代码：

 /** * 测试 迪杰斯特拉 算法的代码 是否实现正确 */ public static void testGraphDijkstra() { String str = \"syztx\"; char[] array = str.toCharArray(); GraphByNode g = new GraphByNode(array,true); g.addEdge(\'s\', \'t\', 10); g.addEdge(\'s\', \'y\', 5); g.addEdge(\'y\', \'t\', 3); g.addEdge(\'y\', \'x\', 9); g.addEdge(\'y\', \'z\', 2); g.addEdge(\'z\', \'s\', 7); g.addEdge(\'z\', \'x\', 6); g.addEdge(\'t\', \'y\', 2); g.addEdge(\'t\', \'x\', 1); g.addEdge(\'x\', \'z\', 4); int[] dist = new int[array.length]; int[] parentPath = new int[array.length]; g.dijkstra(\'s\', dist, parentPath); System.out.println(\"此处可设置端点来调试，观察前面的算法是否正确\"); g.printShortPath(\'s\', dist, parentPath); }

运行结果：

注意：dist 数组 是起始顶点到目标顶点的最短路径。 

上述是 无负权路径的情况，下面我们来看 负权路径的情况：

就需要用到另一种算法：贝尔曼-福得算法。

单源最短路径—Bellman-Ford算法

Dijkstra算法只能用来解决正权图的单源最短路径问题，但有些题目会出现负权图。这时这个算法就不能帮助 我们解决问题了，而bellman—ford算法可以解决负权图的单源最短路径问题。它的优点是可以解决有负权 边的单源最短路径问题，而且可以用来判断是否有负权回路。它也有明显的缺点，它的时间复杂度 O(N*E) (N是点数，E是边数)普遍是要高于Dijkstra算法O(N²)的。像这里如果我们使用邻接矩阵实现，那么遍历所有 边的数量的时间复杂度就是O(N^3)，这里也可以看出来Bellman-Ford就是一种暴力求解更新。

其实 贝尔曼-福特算法总结出来，就一句话：对每条边都进行判断，看是否满足 通过该边 走 比 原来走要更近一些。

代码实现：

邻接矩阵版：

 /** * 贝尔曼-福特算法 * @param vSrc 起始顶点 * @param dist 距离数组 * @param pPath 路径序列数组 * @return 对于负权回路无法求，只能求带有负权的路径 */ public boolean bellmanFord(char vSrc,int[] dist,int[] pPath) { // 与 迪杰斯特拉算法相比，贝尔曼-福特算法只是在 求最短路径上的方法不同 // 前期准备都是一样的 int src = getIndex(vSrc); Arrays.fill(dist, Constant.MAX); dist[src] = 0; Arrays.fill(pPath, -1); // 求最短路径 int n = array.length; for (int k = 0; k < n; k++) { // 可能在经过下面的处理之后，还存在没有完全统计完的边 // 因此循环n次之后，一定的符合要求的 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) {  // 顶点之间存在边 且 换条路长度更短  // 就换条路，并记录下路径序列  if (matrix[i][j] != Constant.MAX && dist[i] + matrix[i][j] < dist[j]) { dist[j] = dist[i] + matrix[i][j]; pPath[j] = i;  } } } } // 但如果是负权回路的话，就不存在最短路径这样的说法 // 因此一直是可以修改的 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // 顶点之间存在边 且 换条路长度更短 if (matrix[i][j] != Constant.MAX && dist[i] + matrix[i][j] < dist[j]) {  return false; } } } // 再走一遭，如果没修改为false就说明不是负权回路，返回true；反之，则返回false return true; }

测试代码： 

 /** * 测试 贝尔曼-福特 算法的代码 是否实现正确 */ public static void testGraphBellmanFord() { String str = \"syztx\"; char[] array = str.toCharArray(); GraphByMatrix g = new GraphByMatrix(array,true); g.addEdge(\'s\', \'t\', 6); g.addEdge(\'s\', \'y\', 7); g.addEdge(\'y\', \'z\', 9); g.addEdge(\'y\', \'x\', -3); g.addEdge(\'z\', \'s\', 2); g.addEdge(\'z\', \'x\', 7); g.addEdge(\'t\', \'x\', 5); g.addEdge(\'t\', \'y\', 8); g.addEdge(\'t\', \'z\', -4); g.addEdge(\'x\', \'t\', -2); int[] dist = new int[array.length]; int[] parentPath = new int[array.length]; boolean flg = g.bellmanFord(\'s\', dist, parentPath); if(flg) { g.printShortPath(\'s\', dist, parentPath); }else { System.out.println(\"存在负权回路\"); } }

运行结果：

邻接表版： 

 /** * 贝尔曼-福特算法 * @param vSrc 起始顶点 * @param dist 距离数组 * @param pPath 路径序列数组 * @return 对于负权回路无法求，只能求带有负权的路径 */ public boolean bellmanFord(char vSrc,int[] dist,int[] pPath) { // 与 迪杰斯特拉算法相比，贝尔曼-福特算法只是在 求最短路径上的方法不同 // 前期准备都是一样的 int src = getIndex(vSrc); Arrays.fill(dist, Constant.MAX); dist[src] = 0; Arrays.fill(pPath, -1); int n = array.length; for (int k = 0; k < n; k++) { // 将所有的边全部遍历一边即可 for (int i = 0; i < n; i++) { Node cur = nodes[i]; while (cur != null) {  int srcI = cur.src;  int dest = cur.dest;  int weight = cur.weight;  if (dist[srcI] + weight < dist[dest]) { dist[dest] = dist[srcI] + weight; pPath[dest] = srcI;  }  cur = cur.next; } } } for (int i = 0; i < n; i++) { Node cur = nodes[i]; while (cur != null) { int srcI = cur.src; int dest = cur.dest; int weight = cur.weight; if (dist[srcI] + weight < dist[dest]) {  return false; } cur = cur.next; } } return true; }

测试代码： 

 /** * 测试 贝尔曼-福特 算法的代码 是否实现正确 */ public static void testGraphBellmanFord() { String str = \"syztx\"; char[] array = str.toCharArray(); GraphByNode g = new GraphByNode(array,true); g.addEdge(\'s\', \'t\', 6); g.addEdge(\'s\', \'y\', 7); g.addEdge(\'y\', \'z\', 9); g.addEdge(\'y\', \'x\', -3); g.addEdge(\'z\', \'s\', 2); g.addEdge(\'z\', \'x\', 7); g.addEdge(\'t\', \'x\', 5); g.addEdge(\'t\', \'y\', 8); g.addEdge(\'t\', \'z\', -4); g.addEdge(\'x\', \'t\', -2); int[] dist = new int[array.length]; int[] parentPath = new int[array.length]; boolean flg = g.bellmanFord(\'s\', dist, parentPath); if(flg) { g.printShortPath(\'s\', dist, parentPath); }else { System.out.println(\"存在负权回路\"); } }

运行结果： 

多源最短路径—Floyd-Warshall算法 

Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。 Floyd算法考虑的是一条最短路径的中间节点，即简单路径p={v1,v2,…,vn}上除v1和vn的任意节点。 设k是p 的一个中间节点，那么从i到j的最短路径p就被分成i到k和k到j的两段最短路径p1，p2。p1是从i到k且中间节 点属于{1，2，…，k-1}取得的一条最短路径。p2是从k到j且中间节点属于{1，2，…，k-1}取得的一条最短路 径。这个也有点暴力枚举的思想，先是计算不通过中间顶点得到的最短路径，再去计算通过中间顶点来计算最短路径。  

代码实现：

 /** * 弗洛伊德算法 * 计算的路径有两种：一种不通过中间顶点，一种是通过中间顶点 * @param dist 距离数组 * @param pPath 路径序列数组 */ public void floydWarShall(int[][] dist, int[][] pPath) { int n = array.length; // 不通过中间顶点去计算路径（就是将矩阵中的值全部复制过去） for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dist[i][j] = matrix[i][j]; pPath[i][j] = matrix[i][j] == Constant.MAX ? -1 : i; } } // 通过中间顶点来计算路径 for (int k = 0; k < n; k++) { // 每个中间顶点都去试一下 for (int i = 0; i < n; i++) { for (int j = 0; j 0->1 || 1->0->0 || 1->1  if (i == k || j == k || i == j) { continue;  }  // 还是去判断是否存在换条路走的更短的情况  // 先看两者是否存在边，再去看是否需要更换  // 注意这里不要写成matrix数组了  if (dist[i][k] != Constant.MAX && dist[k][j] != Constant.MAX && dist[i][k] + dist[k][j] ....->k->....->j (中间顶点k左右并不是i、j) pPath[i][j] = pPath[k][j];  } } } } }

测试代码：

 public static void testGraphFloydWarShall() { String str = \"12345\"; char[] array = str.toCharArray(); GraphByMatrix g = new GraphByMatrix(array,true); g.addEdge(\'1\', \'2\', 3); g.addEdge(\'1\', \'3\', 8); g.addEdge(\'1\', \'5\', -4); g.addEdge(\'2\', \'4\', 1); g.addEdge(\'2\', \'5\', 7); g.addEdge(\'3\', \'2\', 4); g.addEdge(\'4\', \'1\', 2); g.addEdge(\'4\', \'3\', -5); g.addEdge(\'5\', \'4\', 6); int[][] dist = new int[array.length][array.length]; int[][] parentPath = new int[array.length][array.length]; g.floydWarShall(dist,parentPath); // g.printGraph(); for (int i = 0; i < array.length; i++) { System.out.println(\"顶点\"+(i+1)+ \"到其他顶点的最短距离序列与权值（最后一个数）如下所示: \"); g.printShortPath(array[i],dist[i],parentPath[i]); System.out.println(\"==========================\"); } }

运行结果：

因为 弗洛伊德算法 需要申请两个二维数组来存储每个顶点到其他顶点的最短路径 与 序列，因此最好的存储方法就是通过 邻接矩阵来实现，如果是其他的实现方法，就需要去遍历拿出元素再存储到二维数组中，过于麻烦，因此这里就只给出了 邻接矩阵版的。

注意：负权回路问题算是最短路径的一个bug吧，上述的算法都不能解决这个问题。 

一定要注意：无论是 邻接矩阵法 存储图，还是邻接表法存储图，甚至于是十字链表、边集数组等都只是图的存储方式，而这些图的遍历、最小生成树、最短路径这些都是图的操作方法，只要是图都可以进行上述操作，与图的存储方式无关。存储图的方式不同，仅仅只会影响在图中拿数据的方式，例如，邻接矩阵是去遍历数组拿值，而邻接表是去遍历链表拿值。 

好啦！本期 数据结构之图论详解 的学习之旅 就到此结束啦！我们下一期再一起学习吧！