JavaDS —— 图

图的概念

图是由顶点集合以及顶点之间的关系组成的一种数据结构:G = (V,E)
其中 V 表示的是顶点集合 : V = { x | x 属于某个数据对象集} 是有穷非空集合
E 叫做边的集合 : 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)或<vi,vj>。

有向图和无向图:在有向图中,顶点对<x, y>是有序的,顶点对<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>。

在这里插入图片描述

完全图在有n个顶点的无向图中,若有n * (n-1)/2条边,即任意两个顶点之间有且仅有一条边,则称此图为
无向完全图

在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)。

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

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

简单路径与回路:若路径上各顶点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条
边。

图的存储结构

存储图,我们需要保存节点与关系(节点与节点的关系,是否连通,是否带有权重),图的存储结构有两种,一种是邻接矩阵,另一种是邻接表,在后面图的算法中,本文章会以邻接矩阵为例子提供演示。

邻接矩阵

无向图的邻接矩阵是对称的,第i行(列)元素之和,就是顶点i的度。有向图的邻接矩阵则不一定是对称
的,第i行(列)元素之后就是顶点i 的出(入)度。0 表示不连通, 1 表示连通
在这里插入图片描述
如果边带有权值,并且两个节点之间是连通的,上图中的边的关系就用权值代替,如果两个顶点不通,
则使用无穷大代替。
下面代码实现,这里把自己和自己的距离也处理为无穷大,方便后面算法的实现。

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

分析实现

首先通过成员变量,一个存储顶点的数组(当然你也可以使用map 来进行映射,因为后面要获取顶点下标,当顶点个数一多,效率就会低下)
还有必不可少的邻接矩阵——二维数组,用来保存边与边的关系
最后还要有一个布尔类型的变量,因为图有两种,要么是有向图要么是无向图,所以这个变量来保存当前图的类型。

接着就是简单提供构造方法和初始化顶点数组

然后开始写添加边的代码,添加边也很简单,传入三个参数:起始顶点,目标顶点以及权重,我们只要获取到顶点的下标,将其对应到矩阵上就可以完成了,但是要注意无向图的处理,由于无向图是一个对称矩阵,边与边的关系也是双向连通的,所以要单独处理。

最后就是获取度,注意的是有向图的度的获取,有向图的度分为入度和出度。

最终代码

package graph;import java.util.Arrays;public class GraphByMatrix {public char[] arrayV;//顶点数组public int[][] matrix;//邻接矩阵public boolean isDirect;//是否为有向图//构造方法,提供size : 顶点个数//arrayV 顶点数组public GraphByMatrix(int size,boolean isDirect) {this.arrayV = new char[size];matrix = new int[size][size];for (int i = 0; i < matrix.length; i++) {Arrays.fill(matrix[i],Integer.MAX_VALUE);}this.isDirect = isDirect;}//初始化顶点数组public void initArrayV(char[] arrayV) {for (int i = 0; i < arrayV.length; i++) {this.arrayV[i] = arrayV[i];}}//添加边public void addEdge(char srcV, char destV, int weight) {int indexSrc = getIndexV(srcV);int indexDest = getIndexV(destV);matrix[indexSrc][indexDest] = weight;//无向图是对称矩阵,单独处理if(!isDirect) {matrix[indexDest][indexSrc] = weight;}}//获得下标private int getIndexV(char v) {for (int i = 0; i < arrayV.length; i++) {if(arrayV[i] == v) {return i;}}return -1;}//获得顶点的度public int getDegreeOfV(char v) {int count = 0;int index = getIndexV(v);for (int i = 0; i < matrix.length; i++) {if(matrix[index][i] != Integer.MAX_VALUE) {count++;}}//有向图,要单独处理入度if(isDirect) {for (int i = 0; i < matrix.length; i++) {if(i != index && matrix[i][index] != Integer.MAX_VALUE) {count++;}}}return count;}public void printGraph() {for (int i = 0; i < arrayV.length; i++) {System.out.print(arrayV[i] + " ");}System.out.println();for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix.length; j++) {if(matrix[i][j] == Integer.MAX_VALUE) {System.out.print("∞ ");} else {System.out.print(matrix[i][j] + " ");}}System.out.println();}}
}

邻接表

邻接表使用数组表示顶点的集合,使用链表表示边的关系
在这里插入图片描述

注意:无向图中同一条边在邻接表中出现了两次。如果想知道顶点vi的度,只需要知道顶点vi边链表集
合中结点的数目即可。

在这里插入图片描述

有向图中每条边在邻接表中只出现一次,与顶点vi对应的邻接表所含结点的个数,就是该顶点的
出度,也称出度表,要得到vi顶点的入度,必须检测其他所有顶点对应的边链表,看有多少边顶点的dst
取值是i。

在代码的实现中,我们不采用两张表,而是使用一张表处理,就是入边表。

分析实现

首先创建链表的结点:起始位置,目标位置,权重,next 域,构造方法,注意起始位置和目标位置采用 int 类型保存,通过顶点数组来获取下标。

我们使用ArrayList 来实现邻接表,保存链表。
使用char 类型的数组保存顶点
使用 Boolean 类型的变量保存图的类型。

注意ArrayList 的初始化,要对每一个区域赋值为null,如果不这样做,ArrayList 内部的有效数据是为空的,不是 null,这会导致你后面的链表的插入发生越界访问!!!

添加边:
首先我们要先检查这个边是否已经保存进邻接表里了,如果已经有了这条边,就直接返回,如果没有,我们才继续进行添加,添加边的时候,我们采用头插法,然后我们还需要进行考虑无向图,因为无向图的边是双向关系的,所以还要再添加一条边进去。

获得边的度:
无向图:直接遍历对应的链表即可。
但是如果是有向图,我们还需要考虑入度的问题,这时候上面求出了出度,如果是有向图,还需要遍历ArrayList 进行检查。

最终代码

package graph;import java.util.ArrayList;public class GraphByNode {static class Node{public int src;//起始位置public int dest;//目标位置public int weight;//权重public Node next;public Node(int src, int dest, int weight) {this.src = src;this.dest = dest;this.weight = weight;}}public ArrayList<Node> edgeList;//邻接表public boolean isDirect;//是否为有向图public char[] arrayV;//顶点数组//构造方法//注意ArrayList 的处理,如果不赋 null, ArrayList 的有效数据为 0, 无法进行访问的public GraphByNode(int size, boolean isDirect) {this.edgeList = new ArrayList<>(size);for (int i = 0; i < size; i++) {edgeList.add(null);}this.isDirect = isDirect;this.arrayV = new char[size];}//初始化顶点数组public void initArrayV(char[] arrayV) {for (int i = 0; i < arrayV.length; i++) {this.arrayV[i] = arrayV[i];}}//添加边public void addEdge(char src, char dest, int weight) {int indexSrc = getIndexOfV(src);int indexDest = getIndexOfV(dest);addNode(indexSrc,indexDest,weight);//无向图,再次添加if(!isDirect) {addNode(indexDest,indexSrc,weight);}}private void addNode(int indexSrc, int indexDest, int weight) {//首先判断这个节点是否存在Node cur = edgeList.get(indexSrc);while(cur != null) {if(cur.dest == indexDest) {return;}cur = cur.next;}//没有存储,进行存储Node newNode = new Node(indexSrc,indexDest,weight);newNode.next = edgeList.get(indexSrc);edgeList.set(indexSrc,newNode);}//获取下标private int getIndexOfV(char v) {for (int i = 0; i < arrayV.length; i++) {if(arrayV[i] == v) {return i;}}return -1;}//获取度public int getDegreeOfV(char v) {int count = 0;int index = getIndexOfV(v);Node cur = edgeList.get(index);while(cur != null) {count++;cur = cur.next;}//有向图,单独处理入度if(isDirect) {for (int i = 0; i < arrayV.length; i++) {if (i != index) {cur = edgeList.get(i);while (cur != null) {if (cur.dest == index) {count++;}cur = cur.next;}}}}return count;}//打印邻接表public void printGraph() {for (int i = 0; i < arrayV.length; i++) {Node cur = edgeList.get(i);while(cur != null) {System.out.print(cur.dest + ":" + cur.weight + "-> ");cur = cur.next;}System.out.println();}}}

图的遍历

从这里开始,我们以邻接矩阵为例子进行代码的讲解与分析。

图的遍历,以无向图为例

广度优先遍历

在这里插入图片描述
广度优先遍历类似二叉树的层次遍历。

广度优先遍历的英文全称为 Breadth-First Search,简写为 bfs

分析:
类似二叉树的层次遍历,在二叉树的层次遍历我们借助了一个队列,这里我们也使用一个队列来保存顶点。

然后我们开始进行运行,以下面的图为例:
在这里插入图片描述

先从A开始遍历,把A放入队列,在出队列的同时,遍历矩阵把B和C放入队列中,然后进行B的出队列,这时候又遍历矩阵B那行,这时候A和C 进来了,你会发现A重复进来了,所以为例避免这种情况,我们使用一个辅助数组来记录某个顶点是否被遍历了,也就是在出队列和进队列的时候把这个顶点标记为 true,表示已经被遍历过了。

    public void bfs(char src) {int n = arrayV.length;boolean[] check = new boolean[n];//辅助数组Queue<Character> queue = new LinkedList<>();queue.offer(src);while(!queue.isEmpty()) {char ch = queue.poll();System.out.print(ch + " ");int index = getIndexV(ch);check[index] = true;for (int i = 0; i < n; i++) {if(matrix[index][i] != Integer.MAX_VALUE && !check[i]) {queue.offer(arrayV[i]);check[i] = true;}}}System.out.println();}

深度优先遍历

在这里插入图片描述
深度优先遍历类似二叉树的前序遍历。

深度遍历英文全称为Depth First Search,简写为 dfs

思路:
使用一个辅助数据记录当前的顶点是否被访问过
然后我们使用递归,每次遇到未被访问过的顶点,进行递归处理。

    public void dfs(char v) {boolean[] visited = new boolean[arrayV.length];int index = getIndexV(v);dfsChile(index,visited);}private void dfsChile(int index, boolean[] visited) {System.out.print(arrayV[index] + "->");visited[index] = true;for (int i = 0; i < arrayV.length; i++) {if(!visited[i] && matrix[index][i] != Integer.MAX_VALUE) {dfsChile(i,visited);}}}

最小生成树

连通图中的每一棵生成树,都是原图的一个极大无环子图,即:从其中删去任何一条边,生成树 就不在连
通;反之,在其中引入任何一条新边,都会形成一条回路。

若连通图由n个顶点组成,则其生成树必含n个顶点和n-1条边。因此构造最小生成树的准则有三条:

  1. 只能使用图中的边来构造最小生成树
  2. 只能使用恰好n-1条边来连接图中的n个顶点
  3. 选用的n-1条边不能构成回路

构造最小生成树的方法:Kruskal算法和Prim算法。这两个算法都采用了逐步求解的贪心策略

贪心算法:是指在问题求解时,总是做出当前看起来最好的选择。也就是说贪心算法做出的不是整体最优的
的选择,而是某种意义上的局部最优解。贪心算法不是对所有的问题都能得到整体最优解。

Kruskal 算法

KrusKal 算法中文名称为:克鲁斯卡尔算法

任给一个有n个顶点的连通网络N={V,E},
首先构造一个由这n个顶点组成、不含任何边的图G={V,NULL},其中每个顶点自成一个连通分量,
其次不断从E中取出权值最小的一条边(若有多条任取其一),若该边的两个顶点来自不同的连通分量,则将此边加入到G中。
如此重复,直到所有顶点在同一个连通分量上为止。

核心:每次迭代时,选出一条具有最小权值,且两端点不在同一连通分量上的边,加入生成树。

Kruskal 算法采用的是全局贪心策略,即每次都在全图中获取最小的边,并且要求这条边不能构成一条回路。

在这里插入图片描述

我们来过一下Kruskal 算法的流程:
在这里插入图片描述
纵观全图,我们找到 h - g 这条边的全职最小,将其纳入到最小生成树中

在这里插入图片描述

接着再次纵观全图,发现 i - c 或者 g - f 这两条边都是最小,将谁纳入到最小生成树都是可以的,这里我们将 i - c 纳入。

在这里插入图片描述
纵观全图,发现 g - f 最小,纳入生成树中。

在这里插入图片描述
a - b 与 c - f 都是 4 ,将其一纳入即可,这里纳入 a-b

在这里插入图片描述
c-f 进入最小生成树中

在这里插入图片描述
然后你会发现这时候最小的边应该为 i - g ,但是我们的最小生成树要求不能有环,所以这条边不能纳入,然后我们再继续找,这时候 c - d 和 i - h 为最小边,但是由于 i- h 纳入的话,会构成环路,所以只能将 c - d 纳入最小生成树中。

在这里插入图片描述

重复上面的动作,最后得到下面的最小生成树:

在这里插入图片描述

注意最小生成树的结果不是唯一的,只要符合算法思想即可

算法思路分析:
首先我们需要从全图中找到一个最小的边,我们可以使用优先级队列构建小根堆,将全部的边纳入到图中,通过出队列的方式获取最小的边。

然后我们需要判断最小的边会不会构成回路,如果不会才能纳入到最小生成树中。
判断回路:我们可以采用集合的方式,如果这条边的两个顶点都在生成树的集合中,就不能纳入,这时候我们可以使用并查集来判断,如果不了解并查集可以查阅这一篇博客 JavaDS —— 并查集
在每次纳入生成树的同时,将这两个顶点纳入并查集中。

注意生成树要求 n 个顶点加 n- 1 条边,这是有可能满足不了 n - 1 条边的,就像下面的图一样,D 点是隔离的,无法实现最小生成树,这时候你在构建最小生成树的结尾要判断是否构建好了最小生成树,如果没有可以返回 -1


最终代码:

    //创建边类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;}}public int Kruskal(GraphByMatrix minTree) {//创建优先级队列PriorityQueue<Edge> queue = new PriorityQueue<>(new Comparator<Edge>() {@Overridepublic int compare(Edge o1, Edge o2) {return o1.weight - o2.weight;}});//将所有的边纳入到优先级队列中int n = arrayV.length;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if(matrix[i][j] != Integer.MAX_VALUE) {queue.offer(new Edge(i,j,matrix[i][j]));}}}UnionFindSet unionFindSet = new UnionFindSet(n);//构建生成树int size = 0;int totalWeight = 0;while(!queue.isEmpty() && size < n - 1) {Edge tmp = queue.poll();int src = tmp.src;int dest = tmp.dest;if(!unionFindSet.isSameSet(src,dest)) { minTree.addEdge(arrayV[src],arrayV[dest], tmp.weight);unionFindSet.union(src,dest);totalWeight += tmp.weight;size++;}}if(size < n - 1) {return -1;}return totalWeight;}

Prime 算法

Prime 算法 中文名称为 普里姆算法

在这里插入图片描述

在这里插入图片描述

Prime 算法采用局部贪心的策略。

我们来走一下这个算法的流程:

首先给定一个初始的顶点,这里给的是 a
在这里插入图片描述
然后从 d 开始寻找最小边,得到 a - b,将其纳入到最小生成树中。在这里插入图片描述
然后我们得到最小生成树的集合为 {a,b},这时候 b 向外延伸, b - c = 8, b - h = 11, a - h = 8,经过比较,b - c 和 a-h 都是最小边,将其一纳入即可,这里纳入的是 b-c
在这里插入图片描述

现在最小生成树的集合为 {a,b.c}, c 开始延伸,c - i = 2 , c - f = 4, c - d = 7 ,并且和前面的 a-h = 8 进行比较,最后纳入 c - i 这条边。
在这里插入图片描述

i 延伸,i - g = 6, i - h = 7 , 并且和前面的为被纳入的最小边集合进行比较,最后将 c - f 纳入生成树中。

在这里插入图片描述
然后以此类推,最后得到:
在这里插入图片描述

算法分析:
我们还是使用优先级队列保存边的关系,但是prime 算法是每进一个顶点,才会将新顶点所在的边关系全部入队。

首先先将初始顶点的边关系信息入队,然后开始找最小边,然后将最小边的信息纳入到生成树中,并且与之对应的新顶点也要纳入到集合中,新顶点的边关系也随之纳入进去。使用循环来进行操作。

最终代码:

	//创建边类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;}}public int prime(GraphByMatrix minTree, char src) {int totalWeight = 0;int n = arrayV.length;int size = 0;//构建优先级队列PriorityQueue<Edge> queue = new PriorityQueue<>(new Comparator<Edge>() {@Overridepublic int compare(Edge o1, Edge o2) {return o1.weight - o2.weight;}});UnionFindSet unionFindSet = new UnionFindSet(n);int index = getIndexV(src);for (int i = 0; i < n; i++) {if(matrix[index][i] != Integer.MAX_VALUE) {queue.offer(new Edge(index,i,matrix[index][i]));}}while(!queue.isEmpty()) {Edge tmp = queue.poll();int indexSrc = tmp.src;int indexDest = tmp.dest;int weight = tmp.weight;if(!unionFindSet.isSameSet(indexSrc,indexDest)) {unionFindSet.union(indexSrc,indexDest);minTree.addEdge(arrayV[indexSrc],arrayV[indexDest],weight);for (int i = 0; i < n; i++) {if(matrix[indexDest][i] != Integer.MAX_VALUE) {queue.offer(new Edge(index,i,matrix[index][i]));}}totalWeight += weight;size++;}}if(size < n - 1) {return -1;}return totalWeight;}

最短路径

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

Dijkstra算法

迪杰斯特拉算法

单源最短路径问题:给定一个图G = ( V , E ) G=(V,E)G=(V,E),求源结点s ∈ V s∈Vs∈V到图中每个结点v
∈ V v∈Vv∈V的最短路径。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算法存在的问题是不支持图中带负权路径,如果带有负权路径,则可能会找不到一些路径的最短路径。

在这里插入图片描述

    public void dijkstra(char vSrc,int[] dist,int[] pPath) {int srcIndex = getIndexV(vSrc);//距离数据初始化Arrays.fill(dist,Integer.MAX_VALUE);dist[srcIndex] = 0;//路径数组初始化Arrays.fill(pPath,-1);pPath[srcIndex] = 0;//当前顶点是否被访问过?int n = arrayV.length;boolean[] s = new boolean[n];//n个顶点,要更新n次,每次都要从0下标开始,找到一个最小值for (int k = 0; k < n; k++) {int min = Integer.MAX_VALUE;int u = srcIndex;for (int i = 0; i < n; i++) {if(s[i] == false && dist[i] < min) {min = dist[i];u = i;//更新u下标}}s[u] = true;//u:s//松弛u连接出去的所有的顶点 vfor (int v = 0; v < n; v++) {if(s[v] == false && matrix[u][v] != Integer.MAX_VALUE&& dist[u] + matrix[u][v] < dist[v]) {dist[v] = dist[u] + matrix[u][v];pPath[v] = u;//更新当前的路径}}}}

Bellman-Ford算法

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

在这里插入图片描述

    public boolean bellmanFord(char vSrc,int[] dist,int[] pPath) {int srcIndex = getIndexV(vSrc);//距离数据初始化Arrays.fill(dist,Integer.MAX_VALUE);dist[srcIndex] = 0;//路径数组初始化Arrays.fill(pPath,-1);pPath[srcIndex] = 0;int n = arrayV.length;for (int k = 0; k < n; k++) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if(matrix[i][j] != Integer.MAX_VALUE &&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] != Integer.MAX_VALUE &&dist[i] + matrix[i][j] < dist[j]) {return false;}}}return true;}

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}取得的一条最短路
径。

在这里插入图片描述
在这里插入图片描述

Floyd算法本质是三维动态规划,D[i][j][k]表示从点i到点j只经过0到k个点最短路径,然后建立起转移方程,然后通过空间优化,优化掉最后一维度,变成一个最短路径的迭代算法,最后即得到所以点的最短路

    public void floydWarShall(int[][] dist,int[][] pPath) {int n = arrayV.length;for (int i = 0; i < n; i++) {Arrays.fill(dist[i],Integer.MAX_VALUE);Arrays.fill(pPath[i],-1);}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if(matrix[i][j] != Integer.MAX_VALUE) {dist[i][j] = matrix[i][j];pPath[i][j] = i;}else {pPath[i][j] = -1;}if(i == j) {dist[i][j] = 0;pPath[i][j] = -1;}}}for (int k = 0; k < n; k++) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (dist[i][k] != Integer.MAX_VALUE &&dist[k][j] != Integer.MAX_VALUE &&dist[i][k] + dist[k][j] < dist[i][j]) {dist[i][j] = dist[i][k] + dist[k][j];//更新父节点下标//pPath[i][j] = k;//不对//如果经过了 i->k  k->j  此时是k//i->x->s->k   k->..t->...x->jpPath[i][j] = pPath[k][j];}}}}}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/427219.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

UE5源码Windows编译、运行

官方文档 Welcome To Unreal Engine 5 Early Access Learn what to expect from the UE5 Early Access program. 链接如下&#xff1a;https://docs.unrealengine.com/5.0/en-US/Welcome/#gettingue5earlyaccessfromgithub Step 0&#xff1a;找到UE5源码 直接先上链接 https…

MySQL原理之UUID主键分析,插入或更新语法分析

文章目录 1 MySQL不能用UUID做主键1.1 前言1.2 mysql和程序实例1.2.1 准备工作1.2.2 开始测试1.2.3 程序写入结果1.2.4 效率测试结果 1.3 使用uuid和自增id的索引结构对比1.3.1 自增id1.3.2 uuid 1.4 自增id缺点1.5 雪花算法 2 插入或更新2.1 on duplicate key2.1.1 定义2.1.2 …

24年蓝桥杯及攻防世界赛题-MISC-3

21 reverseMe 复制图片&#xff0c;在线ocr识别&#xff0c;https://ocr.wdku.net/&#xff0c;都不费眼睛。 22 misc_pic_again ┌──(holyeyes㉿kali2023)-[~/Misc/tool-misc/zsteg] └─$ zsteg misc_pic_again.png imagedata … text: “$$KaTeX parse error: Undefined…

python基础(1)pyenv安装和对Django使用

pyenv安装 pyenv主要针对类 Unix 系统&#xff08;如 Linux、macOS&#xff09;用户&#xff0c;pyenv-win 是专为 Windows 开发的 pyenv 版本&#xff0c;允许您在不使用 WSL 的情况下管理多个 Python 版本和虚拟环境。 建议Git Bash&#xff1a; Powershell或Git Bash&…

功能测试干了三年,快要废了。。。

8年前刚进入到IT行业&#xff0c;到现在学习软件测试的人越来越多&#xff0c;所以在这我想结合自己的一些看法给大家提一些建议。 最近聊到软件测试的行业内卷&#xff0c;越来越多的转行和大学生进入测试行业&#xff0c;导致软件测试已经饱和了&#xff0c;想要获得更好的待…

Java键盘输入语句

编程输入语句 1.介绍:在编程中&#xff0c;需要接受用户输入的数据&#xff0c;就可以使用键盘输入语句来获取。 2.步骤&#xff1a; 1&#xff09;导入该类的所在包&#xff0c;java.util.* 2)创建该类对象&#xff08;声明变量&#xff09; 3&#xff09;调用里面的功能 3…

任务书与开题报告的区别与联系:如何让二者相辅相成

AIPaperGPT&#xff0c;论文写作神器~ https://www.aipapergpt.com/ 大家好&#xff01;今天咱们聊聊论文写作过程中两个让人又爱又恨的关键步骤&#xff1a;任务书和开题报告。 这两兄弟可是你毕业路上的第一关卡&#xff0c;搞不定它们&#xff0c;你后面别说论文了&#…

时序必读论文12|ICML22 FEDformer基于周期分解的长时序预测transformer架构

论文标题&#xff1a;FEDformer: Frequency Enhanced Decomposed Transformer for Long-term Series Forecasting 开源代码&#xff1a;https://github.com/DAMO-DI-ML/ICML2022-FEDformer 前言 FEDformer这篇文章发表于2022年的ICML。其实如果只比较性能的话&#xff0c;到…

微信如何发布学生查分?教师平台推荐!

学校和老师们都在面临着一个共同的问题&#xff1a;如何高效、便捷地发布学生成绩查询信息&#xff1f;在这个数字化时代&#xff0c;传统的纸质通知和口头传达方式已经无法满足家长和学生的需求。幸运的是&#xff0c;有了易查分这样的在线工具&#xff0c;发布学生查分变得简…

vitis Failed to create the part‘s controls解决方法

类似于 解决方法&#xff1a;重启vitis。 效果&#xff1a; 可以建立lab4了。

wallpaper engine壁纸提取

下载提取软件RavioliGameTools_v2.10.zip https://pan.baidu.com/s/14ZCVw3ucRERsB-GGGoCOqQ 2.运行RExtractor.exe 3.Input file(s)、Output directory填好 4.勾选Allow scanning of unkown files 5.点击Start

Ceph官方文档_01_Ceph简介

目录 Ceph介绍Ceph介绍 Ceph可用于向云平台提供Ceph对象存储,Ceph可用于向云平台提供Ceph块设备服务。Ceph可用于部署Ceph文件系统。所有Ceph存储群集部署开始都是先设置每个Ceph节点,然后再设置网络。 Ceph存储集群需要以下内容:至少一个Ceph监视器和至少一个Ceph管理器,…

vulnhub靶机:Breach 2.1详细过程

下载 下载地址&#xff1a;https://www.vulnhub.com/entry/breach-21,159/ 修改网络模式 根据靶机的描述得知该靶机适用于静态ip&#xff0c;即192.168.110.151&#xff1b;配置虚拟机的虚拟网络编辑器的仅主机模式&#xff0c;将其子网IP配置在110网段&#xff0c;并将攻击…

C++初阶学习第六弹------标准库中的string类

目录 一.标准库中的string类 二.string的常用接口函数 2.1string类对象的构造 2.2 string的容量操作 2.3 string类的访问与遍历 2.4 string类对象的修改 2.5 string类常用的非成员函数 三、总结 一.标准库中的string类 可以简单理解成把string类理解为变长的字符数组&#x…

2024.9.13 Python与图像处理新国大EE5731课程大作业,索贝尔算子计算边缘,高斯核模糊边缘,Haar小波计算边缘

1.编写一个图像二维卷积程序。它应该能够处理任何灰度输入图像&#xff0c;并使用以下内核进行操作&#xff1a; %matplotlib inline import numpy as np import matplotlib.pyplot as plt from scipy import linalg import random as rm import math import cv2# import and …

linux网络编程3

24.9.19学习目录 一.UDP&#xff08;续&#xff09;1.UDP编程2.注意点2.TFTPTFTP通信过程TFTP协议分析 一.UDP&#xff08;续&#xff09; 1.UDP编程 &#xff08;1&#xff09;sendto函数发送数据 向to结构体指针中指定的ip&#xff0c;发送UDP数据&#xff1b; 通过to和ad…

时间复杂度的常用符号+渐进时间复杂度分析

时间复杂度的常用符号 Θ \Theta Θ 如果 f ( n ) Θ ( g ( n ) ) f(n)\Theta(g(n)) f(n)Θ(g(n))&#xff0c;则 f ( n ) f(n) f(n) 与 g ( n ) g(n) g(n) 同阶。&#xff08;阶是指 f ( n ) f(n) f(n) 的指数&#xff0c;比如 n 2 n^2 n2 高于 n n n&#xff09; O O …

MacOS安装homebrew,jEnv,多版本JDK

1 安装homebrew homebrew官网 根据官网提示&#xff0c;运行安装命令 /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)"安装后&#xff0c;bash会提示执行两条命令 (echo; echo eval "$(/opt/homebrew/b…

海康威视摄像机和录像机的监控与回放

文章目录 海康威视摄像机和录像机的监控与回放1、海康威视监控设备简介1.1、摄像机二次开发1.1.1&#xff1a;协议选择 1.2&#xff1a;web集成1.2&#xff1a;标准协议对接1.2.1&#xff1a;ffmpeg软件转流1.2.2&#xff1a;开源监控软件shinobi1.2.3&#xff1a;使用nginx的R…

黑神话悟空mac可以玩吗

黑神话悟空mac上能不能玩对于苹果玩家来说很重要&#xff0c;那么黑神话悟空mac可以玩吗&#xff1f;目前是玩不了了&#xff0c;没有针对ios系统的版本&#xff0c;只能之后在云平台上找找了&#xff0c;大家可以再观望下看看。 黑神话悟空mac可以玩吗 ‌使用CrossOver‌&…