找往期文章包括但不限于本期文章中不懂的知识点：
个人主页：我要学编程(ಥ_ಥ)-CSDN博客
所属专栏：数据结构（Java版）
目录
图的基本概念
图的存储结构
邻接矩阵
邻接表
图的遍历
广度优先遍历（BFS）
深度优先遍历（DFS）
最小生成树
Kruskal算法（克鲁斯卡尔算法）
Prim算法（普利姆算法）
最短路径
单源最短路径 — Dijkstra算法
单源最短路径—Bellman-Ford算法
多源最短路径—Floyd-Warshall算法
图的基本概念
图是由顶点集合及顶点间的关系组成的一种数据结构：G=(V，E)，其中顶点集合V={x|x属于某个数据对象集}是有穷非空集合；E = {(x,y)|x,y属于V}或者E = {<x, y>|x,y属于V && Path(x, y)}是顶点间关系的有穷集合，也叫做边的集合。(x, y)表示x到y的一条双向通路，即(x, y)是无方向的； Path<x, y>表示从x到y的一条单向通路，即Path<x, y>是有方向的。
顶点和边：图中结点称为顶点，第i个顶点记作vi。两个顶点vi和vj相关联称作顶点vi和顶点vj之间有一条边，图中的第k条边记作ek，ek=(vi，vj)或<yi，v>。
有向图和无向图：在有向图中，顶点对是有序的，顶点对<x，y>称为顶点x到顶点y的一条边(弧)，<x，y>和<y，x>是两条不同的边，比如下图G3和G4为有向图。在无向图中，顶点对(x, y)是无序的，顶点对(x,y) 称为顶点x和顶点y相关联的一条边，这条边没有特定方向，(x，y)和(y，x)是同一条边，比如下图G1和G2为 无向图。注意：无向边(x, y)等于有向边<x，y> 和 <y，x>。
上面说了这么多，其实就是说了两件事：
1、图是由顶点与边的一种数据结构，边是连接顶点与顶点之间桥梁；
2、根据顶点间的边是否有方向，图分为两种：一种是无向图，一种是有向图。无向图：边是无方向的，有向图边是有方向的。因此无向图的 顶点a->b的边 与 顶点b->a的边是一样的，但是有向图却不是，这就是方向。有向图的边类似与数学中的向量。
从上面我们也可以看出来，有向图的顶点边是有方向的，且树是一种特殊的图。
完全图：在有n个顶点的无向图中，若有n＊(n-1)/2条边，即任意两个顶点之间有且仅有一条边，则称此图为无向完全图，比如上图G1；在n个顶点的有向图中，若有n＊(n-1)条边，即任意两个顶点之间有且仅有方向相反的边（两条边），则称此图为有向完全图。
邻接顶点：在无向图中G中，若(u,v)是E(G)中的一条边，则称u和v互为邻接顶点，并称边(u,v)依附于顶点u和v；在有向图G中，若<u,v>是E(G)中的一条边，则称顶点u邻接到v，顶点v邻接自顶点u，并称边<u,v>与顶点u和顶点v相关联。
邻接顶点，顾名思义就是相邻相接的顶点，相接也就是有 边 将两者连接起来了，因此就相邻了。
顶点的度：顶点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 < nodes.length; i++) {// 先打印顶点System.out.printf("%c: ", array[i]);Node cur = nodes[i];while (cur != null) {// 不能简单的打印src和dest，而是要打印顶点System.out.printf("%c->%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<Character> 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<Character> 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) {throw new RuntimeException("下标不合法");}// 找到两个顶点的根结点int x_root = getRoot(x);int y_root = getRoot(y);// 判断两个根结点是否一致：判断两者是否是一个集合return x_root == y_root;}/*** 找到x的根结点* @param x 需要找根结点的下标* @return 找到的根结点*/private int getRoot(int x) {// 在前面已经判断过是否合法了while (elem[x] >= 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<Edge> minQ = new PriorityQueue<>(new Comparator<Edge>() {@Overridepublic 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<Edge> minQ = new PriorityQueue<>((o1, o2) -> {return o1.weight-o2.weight;});// 遍历邻接表，将边全部填充到优先级队列中int n = array.length;for (int i = 0; i < n; i++) {Node cur = nodes[i];while (cur != null) {Edge e1 = new Edge(cur.src, cur.dest, cur.weight); // A->BEdge 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<Edge> minQ = new PriorityQueue<>((o1, o2)->{return o1.weight-o2.weight;});int n = array.length;// 将处理的顶点分为一组Set<Character> setX = new HashSet<>();// 将未处理的顶点分为一组Set<Character> 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 < n-1 && !minQ.isEmpty()) {Edge e = minQ.poll();char srcV = array[e.src];char destV = array[e.dest];int weight = e.weight;// 只有当两者不在一个集合中是 ，才不会构成回路if (!setX.contains(destV)) {// 放到最小生成树中。权重更新、最小生成树的边数更新minTree.addEdge(srcV, destV, weight);System.out.println(srcV+"--->"+destV+": "+weight);total += weight;size++;// 集合更新setX.add(destV);setY.remove(destV);// 优先级队列更新index = getIndex(destV);for (int i = 0; i < matrix[index].length; i++) {// 这条边并没有被使用过(a->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<Edge> minQ = new PriorityQueue<>((o1, o2)->{return o1.weight- o2.weight;});// 申请两个集合：// setX，存放已经处理的顶点// setY，存放待处理的顶点Set<Character> setX = new HashSet<>();Set<Character> 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[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<Integer> 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<Integer> 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；反之，则返回falsereturn 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 < n; j++) {// 这三种情况都是不需要更新的(是原来的值)// 0->0->1 || 1->0->0 || 1->1if (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] < dist[i][j]) {dist[i][j] = dist[i][k] + dist[k][j];// pPath[i][j] = k; // 这种情况是不对的，没有考虑全面// i->....->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吧，上述的算法都不能解决这个问题。
一定要注意：无论是 邻接矩阵法 存储图，还是邻接表法存储图，甚至于是十字链表、边集数组等都只是图的存储方式，而这些图的遍历、最小生成树、最短路径这些都是图的操作方法，只要是图都可以进行上述操作，与图的存储方式无关。存储图的方式不同，仅仅只会影响在图中拿数据的方式，例如，邻接矩阵是去遍历数组拿值，而邻接表是去遍历链表拿值。
好啦！本期 数据结构之图论详解 的学习之旅 就到此结束啦！我们下一期再一起学习吧！
