目录图的基本概念图的存储和遍历邻接矩阵邻接表图的遍历构造最小生成树Kruskal算法Prim算法最短路径问题单源最短路径Dijkstra算法Bellman-Ford算法多源最短路径Floyd-Warshall算法参考代码图的基本概念图是由顶点集合及顶点间的关系边组成的一种数据结构用G (V E)表示。其中V是顶点的集合顶点的个数不能为0E是顶点间关系的集合也就是边的集合它的个数可以为0。简单来说图就是由有限个顶点和有限条边组成的。图中第i个顶点记作vii是下标编号没有要求可以自行给顶点和边编号。图中第k条边记作ekk是下标。边有双向和单向之分ekvi,vj表示ek是顶点vi到顶点vj的一条有向边类似单行道在这条边上只能从vi走到vj如果是ekvi,vj则表示ek是顶点vi和顶点vj的一条无向边没有特定的方向其实就是双向的边。其中vi,vj和vi,vj也叫顶点对分为有序和无序vi,vj是有序的也就是有向的所以vi,vj和vj,vi不同无序的顶点对vivj则和vj,vi相同。一个图中只能有一种边要么都是无向边要么都是有向边。如下左边的图只有有向边叫做有向图右边的图则是只有无向边的无向图。如果图中所有能存在的边都已经存在再画一条边就必定会跟其中一条边重复的图就是完全图。有向的叫有向完全图下图左边如果有n个顶点就有有n*(n-1)条边无向的叫无向完全图(下图右边)n个顶点有 n*(n-1)/2条边。在无向图中GVE中若(vi, vj)是E中的一条边则称 vi 和 vj 互为邻接顶点并称边(vi,vj)依附于顶点 vi 和 vj在有向图G中若vi, vj是E中的一条边则称顶点vi邻接到vj顶点vj邻接自顶点vi并称边vi, vj与顶点vi和顶点vj相关联。顶点v的度是指与它相关联的边的条数。在有向图中顶点的度等于该顶点的入度与出度之和其中顶点v的入度是以v为终点的有向边的条数顶点v的出度是以v为起始点的有向边的条数。对于无向图顶点的度与该顶点的入度和出度都相等这是因为无向图的边可以看作双向的边每有一条无向边依附于v就会同时增加一个入度和一个出度。若从顶点vi出发有一组边使其可到达顶点vj则称顶点 vi 到顶点 vj 的顶点序列为从顶点 vi 到顶点 vj 的路径双向的路径记作vi,vj,单向的记作 Path(vi,vj)。权值W是边附带的数据信息对于不带权的图一条路径的路径长度是指该路径上的边的条数对于带权的图如下一条路径的路径长度是指该路径上各个边权值的总和。若路径上各顶点v1v2v3…vm均不重复则称这样的路径为简单路径。若路径上第一个顶点v1和最后一个顶点vm重合则称这样的路径为回路或环。若图G1由图G中的部分顶点和边构成则称G1是G的子图。在无向图中若从顶点v1到顶点v2有路径则称顶点v1与顶点v2是连通的。如果图中任意一对顶点都是连通的则称此图为连通图。在有向图中若在每一对顶点 vi 和 vj 之间都存在一条从 vi 到 vj 的路径也存在一条从 vj 到 vi 的路径则称此有向图是强连通图。一个无向连通图的最小连通子图称作该无向图的生成树也就是用图中最少的边将所有的顶点连接起来有n个顶点的连通图的生成树有n个顶点和n- 1条边如果还能满足边的权值之和也是最小的那就是最小生成树。最小生成树有可能是不唯一的。图的存储和遍历存储的核心就是留下图的所有信息。图只有顶点和边二叉树也是图的一种但图的结构不一定像二叉树那样规则所以要将顶点和边分开存储。顶点没什么好说的一个数组就行主要是边怎么表示和存储。这里有两种办法一种是邻接矩阵一种是邻接表。邻接矩阵用一个二维数组edge存储edge[ i ][ j ] 表示连接顶点 i 和 j 的边的权值在有向图中特指从顶点 i 出发到 j 的边的权值如果权值为无穷大就表示没有这条边。其次将顶点到顶点自身看作权值为0的边即edge[ i ][ i ]0。我们可以发现在有向图的邻接矩阵中第 i 行元素之和就是顶点 i 的出度第 i 列元素之和是顶点 i 的入度。而在无向图中第 i 行元素之和与第 i 列元素之和都等于顶点 i 的度。其次用邻接矩阵存储图的优点是能够快速知道两个顶点是否连通缺陷是如果顶点比较多边比较少时矩阵中存储了大量的0成为系数矩阵比较浪费空间并且两个顶点之间的路径不是很好求。邻接表用一个数组link存储链表只存指向链表的第一个节点的指针将无向边视为一条双向的边如果链表link[ i ]中存储的是所有从顶点 i 出发的边就叫出边表链表节点中除了指针和边的权值之外还会存储边指向的顶点的编号链表中所含结点的个数就是该顶点的出度也称出度表。如果存储的是所有到达顶点 i 的边则是入边表链表节点中存储边出发的顶点的编号。两种表都会存储图中全部的边一般只需实现出边表。也可以用二维数组存储边用链表是为了方便删除边。无向图中同一条边在邻接表中出现了两次。顶点vi的度等于顶点vi边链表集合中结点的数目。有向图中每条边在邻接表中只出现一次如果要在出边表中得到顶点 i 的入度必须检测其他所有顶点对应的边链表看有多少边的终点是 i 入边表也是类似。图的遍历图的遍历一样是广度优先BFS和深度优先DFS两种核心都是从一个顶点出发通过邻接矩阵或邻接表找到顶点进行遍历并在一个bool数组中标记已经遍历过的顶点防止重复遍历。都比较简单不详细展开不过要注意有些图并不能从一个顶点出发就遍历整个图如不连通的无向图或者弱连通的有向图等可以通过bool数组找到没有遍历的顶点然后继续遍历。具体可以参考文末的代码中的BFS函数和DFS函数。构造最小生成树构造最小生成树有两种常见的算法一个是Kruskal算法另一个是Prim算法。在文末的代码中也有实现分别是Kruskal函数和Prim函数。Kruskal算法Kruskal算法的核心是在图的全部边中不断选出权值最小的边同时要检查是否构成环直到选出n-1条边将n个顶点连接起来。在实现时先将顶点全部复制一份给生成树因为顶点肯定都一样再将所有边都放入小根堆中依次选出最小的边用并查集算法检查边连接的两个顶点是否构成环如果连接的两个顶点在并查集中属于同一组团体就会构成环。不了解并查集的话可以看我之前发布的博客进阶数据结构并查集_并查集进阶-CSDN博客 或网上搜索这个算法并不复杂。Prim算法Prim算法的核心是从一个顶点出发在与顶点连接的所有边中选权值最小的那个边这样就连接了两个顶点然后在这两个顶点连接的所有边中选权值最小的边接着是在三个顶点连接的边中选再接着就是四个、五个、六个以此类推。以下是示意图只画了关键部分。为了方便讲述我将这些在图结构中与子图相连但不属于子图的边统称为子图附近的边。Prim的实现同样先把顶点都复制一份接着先把第一个顶点连接的所有边加入小根堆然后不断从小根堆中取出权值最小的边添加到生成树中同时把其连接的新顶点的所有边加入小根堆。由于顶点是一个一个连起来的只需要用bool数组记录哪个顶点在最小生成树中没有连接从小根堆中取边的时候判断一下如果这条边连接的另一个顶点在生成树中没有被连接就不会出现环不需要使用并查集。其次是将重复的边加入到小根堆中的问题重复的边虽然在判断环的时候会被筛掉不会对结果产生影响但也会影响一点效率处理也比较简单小根堆中以及已经添加到生成树中的边都是旧顶点子图中的顶点连接的边我们向小根堆加入的边都是新顶点子图以外的顶点连接的边如果出现边重复那就说明新顶点连接到了旧顶点而前面提到的bool数组就记录了顶点是否被连接也就是顶点是否为子图中的旧顶点将边添加到小根堆之前用bool数组判断新顶点连接的是否为旧顶点即可。最短路径问题顾名思义在带权有向图中从某一顶点出发找到通往另一顶点的路径如果满足路径上的权值之和最小就是最短路径。无向图也可以找最短路径把边看成双向的即可。如何通过给定的一个顶点出发找出到其它所有顶点的最短路径的问题就是单源最短路径问题。如果要找的是任意两个顶点之间的最短路径就是多源最短路径问题。单源最短路径Dijkstra算法Dijkstra算法的前提条件是不能有权值为负数的边否则找的可能不是最短路径其核心是从一个顶点出发将图分为两部分一个是每个点都已经找到最短路径的子图S也就是说S是由各个最短路径组成的子图另一个则是顶点还未找到最短路径的部分Q。如果Q中的顶点u存在最短路径肯定是由S中的某个顶点出发得到的这是因为权值不为负在一条最短路径上起点到沿途每个顶点的路径一定是最短路径。由此可以得出两点第一我们只需在S附近的边中找到满足最短路径的边也就是这条边是其到达的顶点的最短路径的一部分将其连接的Q组的顶点加入S不断扩展S的范围直到延伸至整张图就确定了所有顶点的最短路径。第二我们可以通过数组dist记录每一个顶点在各自最短路径中的前一个顶点下面简称前一个顶点是谁dist[ i ]是 i 顶点的前一个顶点通过不断回溯就能找到起点由此可以确定最短路径比如起点a到d的最短路径是a-b-c-dd的前一个顶点就是c。我们要看d的最短路径就通过数组找到了c现在只需要知道c的最短路径所以又通过数组找到了b于是又变成了要看b的最短路径一直找到起点a就得到了最短路径。那么如何在S附近找到这条满足最短路径的边呢和prim算法有些相似。首先一开始S中只有一个作为起点的顶点从它出发的边中最短的那条肯定满足最短路径我们将其出发的边都放入小根堆找到那条最短的边将其连接的顶点暂时命名为u加入S。接着将从u出发的边都放入小根堆。但这时堆中最短的边就不一定满足最短路径了如下S附近最短的边为60但蓝色顶点的最短路径应该是从顶点出发的100。为此在开始找最短路径前我们先将起点到所有顶点的路径权值之和下称路程值都看作无穷大起点到自身的则看作0或者权值W的缺省值每次向S中加入顶点时对从其出发的所有的边不包括指向S中顶点的边进行松弛操作比如我们要松弛边uv就比较u的路程值边的权值和v的路程的大小前者更小就将v的路程值改成u的路程值与边权的和。如下图将起点a加入s后c和b的路程值分别为100和65均小于原来的无穷大所以都进行更新。同时将从a出发的边放入小根堆选出最小的边也就是从a连接到b的权值65的边。此时比较b原来的路程值 和 a的路程值加上这条边的权值发现一样大故可以将b加入S记录b的前一个顶点是a接着继续更新路程、选边循环往复。具体实现可以参考文末的代码。Dijkstra算法只能处理边权不为负的图如果有负权值的边就需要使用Bellman-Ford算法。Bellman-Ford算法Bellman-Ford算法是一种暴力算法不过不是遍历所有可能的路径而是遍历所有的边最短路径的记录方式和Dijkstra一样需要记录各个顶点的路程值以及各个顶点的前一个顶点初始化也是将起点自身的路程值设为0其它顶点的路程值为无穷大。在遍历所有边的过程中不用管选到的是哪条边能松弛就松弛不停遍历所有边进行松弛直到不能再松弛就得到了所有最短路径。具体来说比如我们遍历到一条从顶点u到顶点v的边首先看起点到u的路程是不是无穷大也就是u有没有更新过路程值如果有就进行松弛操作反之则跳过。有几点说明一下。第一比如有一条路径是a-c-b-e如果在遍历过程中经过松弛操作改成了a-u-b-e这种情况按理来说是要更新e的路程值但我们不需要额外处理因为这个算法会不停的遍历等遍历到边be的时候就会通过松弛操作更新路程值这一轮没遍历到那就下一轮。第二如果图中存在由权值为负的边组成的负权环Bellman-Ford算法也会失效所以是需要判断图中有没有负权环的。第三在没有负权环的情况下。如果顶点数为n那么Bellman-Ford算法最多只会遍历n轮也就是把所有的边遍历n-1次最后一次判断有没有负权环。每轮遍历可以保证至少选出一条边满足最短路径。原因比较抽象感兴趣的可以自行了解。第四Bellman-Ford算法虽然一开始也和Dijkstra算法一样是从起点开始松弛附近的边不断扩展但是由于遍历没有限制很快就能把每个顶点都更新一遍然后再不断缩短路径。它能够处理负权值的原因也在这里。如果后面有负权值的边可能会导致前面的路径连接这条边后反而变短但是Dijkstra算法只看附近的边没法预知哪里会有负权边也不会去处理已经选中的边和顶点所以碰到负权边会失效。而Bellman-Ford算法由于本身比较“吃苦耐劳”不停地遍历所有边所以能应对负权边当然代价就是效率比较低下。最后Bellman-Ford算法也有经过优化的版本SPFA。由于Bellman-Ford算法每轮遍历其实只需松弛那些被修改过路程值的顶点出发的边所以可以用一个队列存储这些顶点出队列时对从该顶点出发的边进行松弛并把修改过路程值的顶点入队列直到队列为空。具体可以看文末的代码里面的BellmanFord函数就是Bellman-Ford算法优化后的SPFA。多源最短路径Floyd-Warshall算法Floyd-Warshall算法也可以处理带有负权边的图其核心是动态规划。对于一个三维数组DD[ i ][ j ][ k ]表示从第 i 个顶点出发只经过前k个顶点中的若干个顶点到达第 j 个顶点的最短路径长度也就是前面说的路程值默认都为无穷大。D[ i ][ j ][ 0 ]则表示从顶点 i 直接连接到顶点 j 的边的权值。 将所有边的权值输入DD[ i ][ i ][ 0 ]设为0D[ 0 ][ j ][ k ]和D[ i ][ 0 ][ k ]没有意义前两个维度中的 i 和 j 的取值都是从1开始只有第三维的k才能取0但在动态规划的过程中k也是从1开始但是会用到k-1。为方便讲述下面将第 t 个顶点称作顶点 t 或者 t。状态转移方程的关键在于怎么从D[ i ][ j ][k-1]得到D[ i ][ j ][ k ]。假设顶点 i 到顶点 j 的最短路径经过顶点k那么 i 到 j 的最短路径长度是 i 到 k 的长度加 k 到 j 的长度即D[ i ][ j ][ k ]D[ i ][ k ][k-1]D[ k ][ j ][k-1]再假设没经过顶点k的情况那就和只经过前k-1个顶点中的若干个顶点没有区别D[ i ][ j ][ k ]D[ i ][ k ][ k-1 ]取二者中的较小者就是最终的状态转移方程D[ i ][ j ][ k ]min{D[ i ][ k ][ k-1 ]D[ k ][ j ][k-1]D[ i ][ k ][k-1]}对于任意的顶点 i 、jD[ i ][ j ][ 0 ]是 i 到 j 的边的权值。k虽然是数组D的第三维但是在循环中是最外层的循环因子。即循环的最外层为while(kn)所以在计算D[ i ][ j ][ k ]时对于任意的 s 、t, D[ s ][ t ][k-1]都是已经处理完成的最优路程值。故可以保证在动态规划的过程中上式右边的各项都是有意义的。其次我们还需要记录各顶点在最短路径中的前一个顶点由于起点是任意的所以需要用二维数组来记录。如我用的是parentparent[ s ][ d ]表示在起点为 s 的最短路径中顶点d的前一个顶点。在前面的转态转移方程中如果 i 到 j 有经过顶点k那么顶点 j 在以 i 为起点的最短路径中的前一个顶点应该是顶点 j 在以k为起点的最短路径中的前一个节点 也就是parent[ i ][ j ]parent[ k ][ j ]这是因为顶点k也不一定是直接连接到 j 的。如果没有经过第k个顶点那前一个顶点就没有变化。降维优化实际上为了节约空间Floyd-Warshall算法会通过在原来的空间上迭代可以将D降为二维。D[ i ][ j ]表示顶点 i 到顶点 j 的最短路径长度。与前面不同的是这里的顶点 i 就是指下标为 i 的顶点顶点 j 同理。初始化时D[ i ][ j ]是顶点 i 到顶点 j 的边的权值D[ i ][ i ]取0其它的取无穷大。不难发现在开始动态规划之前D就是邻接矩阵。接下来我们将在多轮动态规划中不断迭代让D[ i ][ j ]从边的权值变为最短路径长度。首先假设顶点 i 到 j 的最短路径要么经过顶点0要么直连由此进行动态规划。如果有顶点 i 到顶点 j 的最短路径有经过顶点0那么D[ i ][ j ]D[ i ][ 0 ]D[ 0 ][ j ]如果没有则D[ i ][ j ]没有变化所以状态转移方程为D[ i ][ j ]min{D[ i ][ j ] , D[ i ][ 0 ]D[ 0 ][ j ] }此时D中的路径就是有经过顶点集合{ 0 }中若干个顶点的最短路径也就是要么经过0要么没有。接下来假设D[ i ][ j ]是经过顶点集合 {012……k-1}中若干个顶点的最短路径长度k可以等于1我们要由此推广到包含顶点k的情况。不难得到状态转移方程D[ i ][ j ]min{D[ i ][ j ]D[ i ][ k ]D[ k ][ j ]}令k从0增加到编号最大的顶点n-1使用上面这个状态转移方程进行多轮动态规划就可以得到真正的最短路径。前一个顶点的记录和前面一样若有经过顶点k则parent[ i ][ j ]parent[ k ][ j ]如果没有就不变。我们可以发现其实整体的思路没有变化只是不再记录由k的值带来的变化而是通过不断的迭代节省空间。具体可以参考文末的代码。参考代码注意代码只经过了粗略的验证不能保证完全正确只提供大致的思路。头文件和Kruskal算法需要用到的并查集#includeiostream #includemap #includevector #includequeue using namespace std; class Unionfindset { public: Unionfindset(size_t n) : _ufs(n, -1) { } int Findroot(int x) {//找老大返回老大的编号 if (_ufs[x] 0) return x; else return _ufs[x] Findroot(_ufs[x]);//直接让下属连接老大提高找老大的效率 } void Union(int a, int b) {//交友、联合将a看作上司 int ar Findroot(a); int br Findroot(b); if (ar ! br) { _ufs[ar] _ufs[br];//算人数 _ufs[br] ar;//认老大 } } size_t Setsize(int x) {//返回x所在团体的大小 return -_ufs[Findroot(x)]; } size_t count() {//返回团体个数 size_t ans 0; for (auto e : _ufs) { if (e 0) ans; } return ans; } private: vectorint _ufs; };使用邻接矩阵实现的图//用邻接矩阵实现的图 namespace Matrix { templateclass V, class W, W MAX_W INT_MAX, bool Direction false//顶点类型权值类型无穷大是否为有向图 class Graph { typedef GraphV, W, MAX_W, Direction Self; public: Graph() default; Graph(const V* vertexs, size_t n) {//先存顶点边后面再加上 _vertexs vectorV(n, V()); for (int i 0; i n; i) { _vertexs[i] vertexs[i]; _vIndexMap[vertexs[i]] i; } _matrix vectorvectorW (n, vectorW(n, MAX_W)); for (int i 0; i n; i) { _matrix[i][i] 0; } } int GetVertexIndex(const V v) {//返回顶点对应下标 auto it _vIndexMap.find(v); if (it ! _vIndexMap.end()) { return it-second; } else { cout 该顶点不存在 endl; return -1; } } void _AddEdge(size_t srci, size_t dsti, const W w) {//用顶点下标添加边 _matrix[srci][dsti] w; if (!Direction) _matrix[dsti][srci] w; } void AddEdge(const V v1, const V v2, const W w) {//用顶点添加 int sr GetVertexIndex(v1); int ds GetVertexIndex(v2); if (sr -1 || ds -1) return; _AddEdge(sr, ds, w); } void BFS() { if (_vertexs.size() 0) return; queueint que; vectorbool hash(_vertexs.size(), false);//是否被访问过 int count 0;//遍历过的顶点数 while (count ! _vertexs.size()) { for (int i 0; i hash.size(); i) {//找一个没遍历过的入队 if (!hash[i]) { que.push(i); hash[i] true; count; break; } } while (!que.empty()) { cout _vertexs[que.front()] ; for (int j 0; j _matrix.size(); j) { if (_matrix[que.front()][j] ! MAX_W !hash[j]) { hash[j] true; que.push(j); count; } } que.pop(); } cout endl; } } void _DFS_Func(vectorbool hash, int set) {//DFS核心递归函数 if (hash[set]) return; cout _vertexs[set] ; hash[set] true; for (int j 0; j _matrix.size(); j) { if (_matrix[set][j] ! MAX_W) _DFS_Func(hash,j); } } void DFS() {//封装 vectorbool hash(_vertexs.size(), false);//是否被访问过 while (1) { int i; for (i 0; i hash.size(); i) {//检查遍历完了没 if (!hash[i]) break; } if (i ! hash.size()) _DFS_Func(hash, i); else break; cout endl; } } struct Edge {//用于方便构造最小生成树 W _w;//权值 int _src;//该边出发的顶点的值 int _dst;//该边指向的顶点的值 Edge(W w) :_dst(-1), _src(-1), _w(w) {} bool operator(const Edge b) const {//用于堆中的比较 return _w b._w; } }; W Kruskal(Self mintree) {//返回权值总和mintree用于存储最小生成树 if (Direction) { cout 该图为有向图 endl; return W(); } mintree._vertexs _vertexs;//顶点都一样边后面加 //由于没有调用构造函数邻接矩阵要手动初始化 mintree._matrix.resize(_vertexs.size(), vectorW(_vertexs.size(), MAX_W)); priority_queueEdge, vectorEdge, greaterEdge edgeque;//小根堆存储所有边 for (int i 0; i _matrix.size(); i) { for (int j 0; j i; j) { if (_matrix[i][j] ! MAX_W){ Edge temp(_matrix[i][j]); temp._src i; temp._dst j; edgeque.push(temp); } } } Unionfindset ufs(_vertexs.size());//并查集 int count 1;//用于判断是不是生成树 W sumW();//计算权值之和 while (count!_vertexs.size() !edgeque.empty()) { Edge temp edgeque.top(); edgeque.pop(); if (ufs.Findroot(temp._src) ! ufs.Findroot(temp._dst)) {//用并查集判断是否构成环 ufs.Union(temp._src, temp._dst); mintree._AddEdge(temp._src, temp._dst, temp._w); sum temp._w; count; } } if (count _vertexs.size()) return sum;//判断是不是生成树 else return W(); } W Prim(Self mintree, V src) {//st是起点 if (Direction) { cout 该图为有向图 endl; return W(); } mintree._vertexs _vertexs;//顶点都一样边后面加 //由于没有调用构造函数邻接矩阵要手动初始化 mintree._matrix.resize(_vertexs.size(), vectorW(_vertexs.size(), MAX_W)); size_t st _vIndexMap[src]; vectorbool hash(_vertexs.size(), true);//记录未连接的顶点 hash[st] false; priority_queueEdge,vectorEdge,greaterEdge edgeque;//小根堆存储附近的所有边 for (int i st; i _matrix[st].size(); i) { if (_matrix[st][i] ! MAX_W i!st) { Edge temp(_matrix[st][i]); temp._src st; temp._dst i; edgeque.push(temp); } } int count 1; W sum W(); while (count ! _vertexs.size() !edgeque.empty()) { Edge temp edgeque.top(); edgeque.pop(); if (hash[temp._dst]) { hash[temp._dst] false; mintree._AddEdge(temp._src, temp._dst, temp._w); count; sum temp._w; for (int j 0; j _matrix[temp._dst].size(); j) {//连接的顶点的所有边加入堆 if (_matrix[temp._dst][j] ! MAX_W hash[j]) {//hash[j]防止连到旧顶点和同一个顶点优化一点效率 Edge t(_matrix[temp._dst][j]); t._src temp._dst; t._dst j; edgeque.push(t); } } } } if (count _vertexs.size()) return sum;//判断是不是生成树 else return W(); } //包含从起点出发到所有顶点的最短路径的信息 void Dijkstra(V srci, vectorW path, vectorint parent) { size_t N _vertexs.size(); int sr _vIndexMap[srci]; path.resize(N, MAX_W);//到各个顶点的最短路径的长度 parent.resize(N, -1);//各个顶点的在各自最短路径中的上一个节点下面简称父节点不断回溯即可确定其最短路径值为-1表示父节点是自己 vectorbool hash(N, false);//true表示该顶点属于找到最短路径的S反之则属于未处理的Q priority_queueEdge, vectorEdge, greaterEdge edgeque;//小根堆存储附近的所有边 path[sr] W(); Edge t(0); t._dst sr; t._src sr; edgeque.push(t); while (!edgeque.empty()) { int cur edgeque.top()._dst;//取的是顶点而不是边 //判断一下从这条边到达是不是最短路径是的话要更新路径长度和父节点 if (path[edgeque.top()._src] edgeque.top()._w path[edgeque.top()._dst]) { path[edgeque.top()._dst] path[edgeque.top()._src] edgeque.top()._w; parent[edgeque.top()._dst] edgeque.top()._src; } edgeque.pop(); if (hash[cur]) continue; hash[cur] true; for (int j 0; j N; j) { if (hash[j] || _matrix[cur][j] MAX_W) continue; Edge temp(_matrix[cur][j]); temp._src cur; temp._dst j; edgeque.push(temp); if (path[cur] _matrix[cur][j] path[j]) {//松弛父节点会在取出边时更新 path[j] path[cur] _matrix[cur][j]; } } } } bool BellmanFord(V srci, vectorW path, vectorint parent) { size_t N _vertexs.size(); int sr _vIndexMap[srci]; path.resize(N, MAX_W);//到各个顶点的最短路径的长度 parent.resize(N, -1);//各个顶点的在各自最短路径中的上一个节点下面简称父节点不断回溯即可确定其最短路径值为-1表示父节点是自己 vectorint count(N, 0);//记录每个顶点遍历次数防止负权环带来的死循环 queueint verque;//顶点队列 vectorboolhash(N, false);//记录顶点是否在队列里防重复 path[sr] 0; verque.push(sr); hash[sr] true; while (!verque.empty()) { int temp verque.front(); verque.pop(); hash[temp] false; count[temp]; if (count[temp] N) return false; for (int j 0; j N; j) { if (_matrix[temp][j]!MAX_W path[j] _matrix[temp][j] path[temp]) { path[j] _matrix[temp][j] path[temp]; parent[j] temp; if (!hash[j]) { verque.push(j);; hash[j] true; } } } } return true; } void FloydWarShall(vectorvectorW path, vectorvectorint parent) {//path就是D size_t N _vertexs.size(); path _matrix;//初始时就是邻接矩阵 parent.resize(N, vectorint(N, -1)); for (int i 0; i N; i) { for (int j 0; j N; j) { if (_matrix[i][j] ! MAX_W i ! j) parent[i][j] i;//父节点也要初始化 } } for (int k 0; k N; k) { for (int i 0; i N; i) { for (int j 0; j N; j) { if (path[i][k] ! MAX_W path[k][j] ! MAX_W i ! j path[i][j] path[i][k] path[k][j]) {//有经过顶点k path[i][j] path[i][k] path[k][j]; parent[i][j] parent[k][j]; } } } } } void Print() {//输出图的内容 for (auto i : _vertexs) {//打印顶点与下标关系 cout i ; } cout endl; for (int i 0; i _vertexs.size(); i) cout i ; cout endl endl; for (auto i : _matrix) {//打印邻接矩阵 for (auto j : i) { if (j ! MAX_W) cout j ; else cout # ; } cout endl; } cout endl; int sup; for (int i 0; i _matrix.size(); i) {//打印所有的边 if (Direction) sup _matrix[i].size(); else sup i; for (int j 0; j sup; j) { if (_matrix[i][j] ! MAX_W Direction) cout _vertexs[i] -- _matrix[i][j] -- _vertexs[j] endl; else if (_matrix[i][j] ! MAX_W) cout _vertexs[i] -- _matrix[i][j] -- _vertexs[j] endl; } } } void PrinrtShotPath(V srci, vectorW dist, vectorint parent) {//打印以srci为起点的所有最短路径 int sr _vIndexMap[srci]; for (int i 0; i parent.size(); i) { if (i sr) continue; vectorint path; int cur i; while (cur ! -1) { path.push_back(cur); cur parent[cur]; } cout 最短路径: endl; for (int i path.size() - 1; i 0; i--) { cout _vertexs[path[i]] -; } cout endl; cout 长度 dist[i] endl endl; } } private: vectorV _vertexs;//顶点 mapV, int _vIndexMap;//映射顶点-编号 vectorvectorW _matrix;//邻接矩阵 }; }使用邻接表实现的图//用邻接表实现的图 namespace Link_Table { templateclass W struct Edge { W _w;//权值 int _src;//该边出发的顶点的值 int _dst;//该边指向的顶点的值 EdgeW* _next; Edge(W w) :_dst(-1), _src(-1), _w(w), _next(nullptr) { } bool operator(const Edge b) const {//用于堆中的比较 return _w b._w; } }; templateclass V, class W, W MAX_W INT_MAX, bool Direction false//顶点类型权值类型无穷大是否为有向图 class Graph { typedef EdgeW Edge; typedef GraphV, W, MAX_W, Direction Self; public: Graph() default; Graph(const V* vertexs, size_t n) {//先存顶点边后面再加上 _vertexs vectorV(n, V()); for (int i 0; i n; i) { _vertexs[i] vertexs[i]; _vIndexMap[vertexs[i]] i; } _LinkTable.resize(n, nullptr); } int GetVertexIndex(const V v) {//返回顶点对应下标 auto it _vIndexMap.find(v); if (it ! _vIndexMap.end()) { return it-second; } else { cout 该顶点不存在 endl; return -1; } } void _AddEdge(size_t sr, size_t ds, const W w) {//用顶点下标添加边 if (sr _vertexs.size() || ds _vertexs.size() || _LinkTable[sr] _LinkTable[sr]-_dst ds)//顶点不存在或者边已经有了 return; Edge* temp new Edge(w); temp-_src sr; temp-_dst ds; //头插也只能头插 temp-_next _LinkTable[sr]; _LinkTable[sr] temp; if (!Direction) {//无向图要再加一条反过来的 _AddEdge(ds, sr, w); } } void AddEdge(const V v1, const V v2, const W w) {//用顶点添加边 int sr GetVertexIndex(v1); int ds GetVertexIndex(v2); if (sr -1 || ds -1) return; _AddEdge(sr, ds, w); } void BFS() { if (_vertexs.size() 0) return; queueint que; vectorbool hash(_vertexs.size(), false);//是否被访问过 int count 0;//遍历过的顶点数 while (count ! _vertexs.size()) { for (int i 0; i hash.size(); i) {//找一个没遍历过的入队 if (!hash[i]) { que.push(i); hash[i] true; count; break; } } while (!que.empty()) { cout _vertexs[que.front()] ; Edge* cur _LinkTable[que.front()]; while (cur) { hash[cur-_dst] true; count; que.push(cur-dst); cur cur-_next; } que.pop(); } cout endl; } } void _DFS_Func(vectorbool hash, int set) {//DFS核心递归函数 if (hash[set]) return; cout _vertexs[set] ;//遍历当前顶点 hash[set] true; Edge* cur _LinkTable[set];//寻找下一个顶点 while (cur) { _DFS_Func(hash, cur-_dst); cur cur-_next; } } void DFS() {//封装 vectorbool hash(_vertexs.size(), false);//是否被访问过 while (1) { int i; for (i 0; i hash.size(); i) {//检查遍历完了没 if (!hash[i]) break; } if (i ! hash.size()) _DFS_Func(hash, i);//开始递归 else break; cout endl; } } W Kruskal(Self mintree) {//返回权值总和mintree用于存储最小生成树 if (Direction) { cout 该图为有向图 endl; return W(); } mintree._vertexs _vertexs;//顶点都一样边后面加 //由于没有调用构造函数邻接表要手动初始化 mintree._LinkTable.resize(_vertexs.size(), nullptr); priority_queueEdge, vectorEdge, greaterEdge edgeque;//小根堆存储所有边 for (int i 0; i _LinkTable.size(); i) { Edge* cur _LinkTable[i]; while (cur) { edgeque.push(*cur); cur cur-_next; } } Unionfindset ufs(_vertexs.size());//并查集 int count 1;//用于判断是不是生成树 W sum W();//计算权值之和 while (count ! _vertexs.size() !edgeque.empty()) { Edge temp edgeque.top(); edgeque.pop(); if (ufs.Findroot(temp._src) ! ufs.Findroot(temp._dst)) {//用并查集判断是否构成环 ufs.Union(temp._src, temp._dst); mintree._AddEdge(temp._src, temp._dst, temp._w); sum temp._w; count; } } if (count _vertexs.size()) return sum;//判断是不是生成树 else return W(); } W Prim(Self mintree, V src) {//src是起点 if (Direction) { cout 该图为有向图 endl; return W(); } mintree._vertexs _vertexs;//顶点都一样边后面加 //由于没有调用构造函数邻接表要手动初始化 mintree._LinkTable.resize(_vertexs.size(), nullptr); size_t st _vIndexMap[src]; vectorbool hash(_vertexs.size(), true);//记录未连接的顶点 hash[st] false; priority_queueEdge, vectorEdge, greaterEdge edgeque;//小根堆存储附近的所有边 Edge* cur _LinkTable[st]; while (cur) { edgeque.push(*cur); cur cur-_next; } int count 1; W sum W(); while (count ! _vertexs.size() !edgeque.empty()) { Edge temp edgeque.top(); edgeque.pop(); if (hash[temp._dst]) { hash[temp._dst] false; mintree._AddEdge(temp._src, temp._dst, temp._w); count; sum temp._w; Edge* cur _LinkTable[temp._dst]; while (cur) { if (hash[cur-_dst]) edgeque.push(*cur); cur cur-_next; } } } if (count _vertexs.size()) return sum;//判断是不是生成树 else return W(); } //包含从起点出发到所有顶点的最短路径的信息 void Dijkstra(V srci, vectorW path, vectorint parent) { size_t N _vertexs.size(); int sr _vIndexMap[srci]; path.resize(N, MAX_W);//到各个顶点的最短路径的长度 parent.resize(N, -1);//各个顶点的在各自最短路径中的上一个节点下面简称父节点不断回溯即可确定其最短路径值为-1表示父节点是自己 vectorbool hash(N, false);//true表示该顶点属于找到最短路径的S反之则属于未处理的Q priority_queueEdge, vectorEdge, greaterEdge edgeque;//小根堆存储附近的所有边 path[sr] W(); Edge t(0); t._dst sr; t._src sr; edgeque.push(t); while (!edgeque.empty()) { int cur edgeque.top()._dst;//取的是顶点而不是边 //判断一下从这条边到达是不是最短路径是的话要更新路径长度和父节点 if (path[edgeque.top()._src] edgeque.top()._w path[edgeque.top()._dst]) { path[edgeque.top()._dst] path[edgeque.top()._src] edgeque.top()._w; parent[edgeque.top()._dst] edgeque.top()._src; } edgeque.pop(); if (hash[cur]) continue; hash[cur] true; Edge* ep _LinkTable[cur];//附近的边加入堆中 while (ep) { if (!hash[ep-_dst]) { edgeque.push(*ep); if (path[cur] ep-_w path[ep-_dst]) {//松弛父节点会在取出边时更新 path[ep-_dst] path[cur] ep-_w; } } ep ep-_next; } } } bool BellmanFord(V srci, vectorW path, vectorint parent) { size_t N _vertexs.size(); int sr _vIndexMap[srci]; path.resize(N, MAX_W);//到各个顶点的最短路径的长度 parent.resize(N, -1);//各个顶点的在各自最短路径中的上一个节点下面简称父节点不断回溯即可确定其最短路径值为-1表示父节点是自己 vectorint count(N, 0);//记录每个顶点遍历次数防止负权环带来的死循环 queueint verque;//顶点队列 vectorboolhash(N, false);//记录顶点是否在队列里防重复 path[sr] 0; verque.push(sr); hash[sr] true; while (!verque.empty()) { int temp verque.front(); verque.pop(); hash[temp] false; count[temp]; if (count[temp] N) return false; Edge* cur _LinkTable[temp]; while (cur) { if (path[cur-_dst] cur-_w path[cur-_src]) {//松弛 path[cur-_dst] cur-_w path[cur-_src]; parent[cur-_dst] cur-_src; if (!hash[cur-_dst]) { verque.push(cur-_dst); hash[cur-_dst] true; } } cur cur-_next; } } return true; } void FloydWarShall(vectorvectorW path, vectorvectorint parent) {//path就是D size_t N _vertexs.size(); path.resize(N, vectorW(N, MAX_W));//初始化 parent.resize(N, vectorint(N, -1)); for (int i 0; i N; i) { Edge* cur _LinkTable[i]; while (cur) { path[cur-_src][cur-_dst] cur-_w; parent[cur-_src][cur-_dst] cur-_src;//父节点也要初始化 cur cur-_next; } path[i][i] W(); } for (int k 0; k N; k) { for (int i 0; i N; i) { for (int j 0; j N; j) { if (path[i][k] ! MAX_W path[k][j] ! MAX_W i ! j path[i][j] path[i][k] path[k][j]) {//有经过顶点k path[i][j] path[i][k] path[k][j]; parent[i][j] parent[k][j]; } } } } } void Print() {//输出图的内容 for (auto i : _vertexs) {//打印顶点与下标关系 cout i ; } cout endl; for (int i 0; i _vertexs.size(); i) cout i ; cout endl endl; for (int i 0; i _LinkTable.size(); i) {//打印邻接表 if (_LinkTable[i]) { cout _vertexs[i] ( i ): ; Edge* cur _LinkTable[i]; while (cur) { cout _vertexs[cur-_dst] ( cur-_dst ) --cur-_w-- ; cur cur-_next; } cout nullptr endl; } else cout _vertexs[i] ( i ): nullptrendl; } } void PrinrtShotPath(V srci, vectorW dist, vectorint parent) {//打印以srci为起点的所有最短路径 int sr _vIndexMap[srci]; for(int i0;iparent.size();i) { if (i sr) continue; vectorint path; int cur i; while (cur ! -1) { path.push_back(cur); cur parent[cur]; } cout 最短路径: endl; for (int i path.size() - 1; i 0; i--) { cout _vertexs[path[i]] -; } cout endl; cout 长度 dist[i] endlendl; } } private: vectorV _vertexs;//顶点 mapV, int _vIndexMap;//映射顶点-编号 vectorEdge* _LinkTable;//邻接表出边表 }; }
（进阶数据结构）图论
目录图的基本概念图的存储和遍历邻接矩阵邻接表图的遍历构造最小生成树Kruskal算法Prim算法最短路径问题单源最短路径Dijkstra算法Bellman-Ford算法多源最短路径Floyd-Warshall算法参考代码图的基本概念图是由顶点集合及顶点间的关系边组成的一种数据结构用G (V E)表示。其中V是顶点的集合顶点的个数不能为0E是顶点间关系的集合也就是边的集合它的个数可以为0。简单来说图就是由有限个顶点和有限条边组成的。图中第i个顶点记作vii是下标编号没有要求可以自行给顶点和边编号。图中第k条边记作ekk是下标。边有双向和单向之分ekvi,vj表示ek是顶点vi到顶点vj的一条有向边类似单行道在这条边上只能从vi走到vj如果是ekvi,vj则表示ek是顶点vi和顶点vj的一条无向边没有特定的方向其实就是双向的边。其中vi,vj和vi,vj也叫顶点对分为有序和无序vi,vj是有序的也就是有向的所以vi,vj和vj,vi不同无序的顶点对vivj则和vj,vi相同。一个图中只能有一种边要么都是无向边要么都是有向边。如下左边的图只有有向边叫做有向图右边的图则是只有无向边的无向图。如果图中所有能存在的边都已经存在再画一条边就必定会跟其中一条边重复的图就是完全图。有向的叫有向完全图下图左边如果有n个顶点就有有n*(n-1)条边无向的叫无向完全图(下图右边)n个顶点有 n*(n-1)/2条边。在无向图中GVE中若(vi, vj)是E中的一条边则称 vi 和 vj 互为邻接顶点并称边(vi,vj)依附于顶点 vi 和 vj在有向图G中若vi, vj是E中的一条边则称顶点vi邻接到vj顶点vj邻接自顶点vi并称边vi, vj与顶点vi和顶点vj相关联。顶点v的度是指与它相关联的边的条数。在有向图中顶点的度等于该顶点的入度与出度之和其中顶点v的入度是以v为终点的有向边的条数顶点v的出度是以v为起始点的有向边的条数。对于无向图顶点的度与该顶点的入度和出度都相等这是因为无向图的边可以看作双向的边每有一条无向边依附于v就会同时增加一个入度和一个出度。若从顶点vi出发有一组边使其可到达顶点vj则称顶点 vi 到顶点 vj 的顶点序列为从顶点 vi 到顶点 vj 的路径双向的路径记作vi,vj,单向的记作 Path(vi,vj)。权值W是边附带的数据信息对于不带权的图一条路径的路径长度是指该路径上的边的条数对于带权的图如下一条路径的路径长度是指该路径上各个边权值的总和。若路径上各顶点v1v2v3…vm均不重复则称这样的路径为简单路径。若路径上第一个顶点v1和最后一个顶点vm重合则称这样的路径为回路或环。若图G1由图G中的部分顶点和边构成则称G1是G的子图。在无向图中若从顶点v1到顶点v2有路径则称顶点v1与顶点v2是连通的。如果图中任意一对顶点都是连通的则称此图为连通图。在有向图中若在每一对顶点 vi 和 vj 之间都存在一条从 vi 到 vj 的路径也存在一条从 vj 到 vi 的路径则称此有向图是强连通图。一个无向连通图的最小连通子图称作该无向图的生成树也就是用图中最少的边将所有的顶点连接起来有n个顶点的连通图的生成树有n个顶点和n- 1条边如果还能满足边的权值之和也是最小的那就是最小生成树。最小生成树有可能是不唯一的。图的存储和遍历存储的核心就是留下图的所有信息。图只有顶点和边二叉树也是图的一种但图的结构不一定像二叉树那样规则所以要将顶点和边分开存储。顶点没什么好说的一个数组就行主要是边怎么表示和存储。这里有两种办法一种是邻接矩阵一种是邻接表。邻接矩阵用一个二维数组edge存储edge[ i ][ j ] 表示连接顶点 i 和 j 的边的权值在有向图中特指从顶点 i 出发到 j 的边的权值如果权值为无穷大就表示没有这条边。其次将顶点到顶点自身看作权值为0的边即edge[ i ][ i ]0。我们可以发现在有向图的邻接矩阵中第 i 行元素之和就是顶点 i 的出度第 i 列元素之和是顶点 i 的入度。而在无向图中第 i 行元素之和与第 i 列元素之和都等于顶点 i 的度。其次用邻接矩阵存储图的优点是能够快速知道两个顶点是否连通缺陷是如果顶点比较多边比较少时矩阵中存储了大量的0成为系数矩阵比较浪费空间并且两个顶点之间的路径不是很好求。邻接表用一个数组link存储链表只存指向链表的第一个节点的指针将无向边视为一条双向的边如果链表link[ i ]中存储的是所有从顶点 i 出发的边就叫出边表链表节点中除了指针和边的权值之外还会存储边指向的顶点的编号链表中所含结点的个数就是该顶点的出度也称出度表。如果存储的是所有到达顶点 i 的边则是入边表链表节点中存储边出发的顶点的编号。两种表都会存储图中全部的边一般只需实现出边表。也可以用二维数组存储边用链表是为了方便删除边。无向图中同一条边在邻接表中出现了两次。顶点vi的度等于顶点vi边链表集合中结点的数目。有向图中每条边在邻接表中只出现一次如果要在出边表中得到顶点 i 的入度必须检测其他所有顶点对应的边链表看有多少边的终点是 i 入边表也是类似。图的遍历图的遍历一样是广度优先BFS和深度优先DFS两种核心都是从一个顶点出发通过邻接矩阵或邻接表找到顶点进行遍历并在一个bool数组中标记已经遍历过的顶点防止重复遍历。都比较简单不详细展开不过要注意有些图并不能从一个顶点出发就遍历整个图如不连通的无向图或者弱连通的有向图等可以通过bool数组找到没有遍历的顶点然后继续遍历。具体可以参考文末的代码中的BFS函数和DFS函数。构造最小生成树构造最小生成树有两种常见的算法一个是Kruskal算法另一个是Prim算法。在文末的代码中也有实现分别是Kruskal函数和Prim函数。Kruskal算法Kruskal算法的核心是在图的全部边中不断选出权值最小的边同时要检查是否构成环直到选出n-1条边将n个顶点连接起来。在实现时先将顶点全部复制一份给生成树因为顶点肯定都一样再将所有边都放入小根堆中依次选出最小的边用并查集算法检查边连接的两个顶点是否构成环如果连接的两个顶点在并查集中属于同一组团体就会构成环。不了解并查集的话可以看我之前发布的博客进阶数据结构并查集_并查集进阶-CSDN博客 或网上搜索这个算法并不复杂。Prim算法Prim算法的核心是从一个顶点出发在与顶点连接的所有边中选权值最小的那个边这样就连接了两个顶点然后在这两个顶点连接的所有边中选权值最小的边接着是在三个顶点连接的边中选再接着就是四个、五个、六个以此类推。以下是示意图只画了关键部分。为了方便讲述我将这些在图结构中与子图相连但不属于子图的边统称为子图附近的边。Prim的实现同样先把顶点都复制一份接着先把第一个顶点连接的所有边加入小根堆然后不断从小根堆中取出权值最小的边添加到生成树中同时把其连接的新顶点的所有边加入小根堆。由于顶点是一个一个连起来的只需要用bool数组记录哪个顶点在最小生成树中没有连接从小根堆中取边的时候判断一下如果这条边连接的另一个顶点在生成树中没有被连接就不会出现环不需要使用并查集。其次是将重复的边加入到小根堆中的问题重复的边虽然在判断环的时候会被筛掉不会对结果产生影响但也会影响一点效率处理也比较简单小根堆中以及已经添加到生成树中的边都是旧顶点子图中的顶点连接的边我们向小根堆加入的边都是新顶点子图以外的顶点连接的边如果出现边重复那就说明新顶点连接到了旧顶点而前面提到的bool数组就记录了顶点是否被连接也就是顶点是否为子图中的旧顶点将边添加到小根堆之前用bool数组判断新顶点连接的是否为旧顶点即可。最短路径问题顾名思义在带权有向图中从某一顶点出发找到通往另一顶点的路径如果满足路径上的权值之和最小就是最短路径。无向图也可以找最短路径把边看成双向的即可。如何通过给定的一个顶点出发找出到其它所有顶点的最短路径的问题就是单源最短路径问题。如果要找的是任意两个顶点之间的最短路径就是多源最短路径问题。单源最短路径Dijkstra算法Dijkstra算法的前提条件是不能有权值为负数的边否则找的可能不是最短路径其核心是从一个顶点出发将图分为两部分一个是每个点都已经找到最短路径的子图S也就是说S是由各个最短路径组成的子图另一个则是顶点还未找到最短路径的部分Q。如果Q中的顶点u存在最短路径肯定是由S中的某个顶点出发得到的这是因为权值不为负在一条最短路径上起点到沿途每个顶点的路径一定是最短路径。由此可以得出两点第一我们只需在S附近的边中找到满足最短路径的边也就是这条边是其到达的顶点的最短路径的一部分将其连接的Q组的顶点加入S不断扩展S的范围直到延伸至整张图就确定了所有顶点的最短路径。第二我们可以通过数组dist记录每一个顶点在各自最短路径中的前一个顶点下面简称前一个顶点是谁dist[ i ]是 i 顶点的前一个顶点通过不断回溯就能找到起点由此可以确定最短路径比如起点a到d的最短路径是a-b-c-dd的前一个顶点就是c。我们要看d的最短路径就通过数组找到了c现在只需要知道c的最短路径所以又通过数组找到了b于是又变成了要看b的最短路径一直找到起点a就得到了最短路径。那么如何在S附近找到这条满足最短路径的边呢和prim算法有些相似。首先一开始S中只有一个作为起点的顶点从它出发的边中最短的那条肯定满足最短路径我们将其出发的边都放入小根堆找到那条最短的边将其连接的顶点暂时命名为u加入S。接着将从u出发的边都放入小根堆。但这时堆中最短的边就不一定满足最短路径了如下S附近最短的边为60但蓝色顶点的最短路径应该是从顶点出发的100。为此在开始找最短路径前我们先将起点到所有顶点的路径权值之和下称路程值都看作无穷大起点到自身的则看作0或者权值W的缺省值每次向S中加入顶点时对从其出发的所有的边不包括指向S中顶点的边进行松弛操作比如我们要松弛边uv就比较u的路程值边的权值和v的路程的大小前者更小就将v的路程值改成u的路程值与边权的和。如下图将起点a加入s后c和b的路程值分别为100和65均小于原来的无穷大所以都进行更新。同时将从a出发的边放入小根堆选出最小的边也就是从a连接到b的权值65的边。此时比较b原来的路程值 和 a的路程值加上这条边的权值发现一样大故可以将b加入S记录b的前一个顶点是a接着继续更新路程、选边循环往复。具体实现可以参考文末的代码。Dijkstra算法只能处理边权不为负的图如果有负权值的边就需要使用Bellman-Ford算法。Bellman-Ford算法Bellman-Ford算法是一种暴力算法不过不是遍历所有可能的路径而是遍历所有的边最短路径的记录方式和Dijkstra一样需要记录各个顶点的路程值以及各个顶点的前一个顶点初始化也是将起点自身的路程值设为0其它顶点的路程值为无穷大。在遍历所有边的过程中不用管选到的是哪条边能松弛就松弛不停遍历所有边进行松弛直到不能再松弛就得到了所有最短路径。具体来说比如我们遍历到一条从顶点u到顶点v的边首先看起点到u的路程是不是无穷大也就是u有没有更新过路程值如果有就进行松弛操作反之则跳过。有几点说明一下。第一比如有一条路径是a-c-b-e如果在遍历过程中经过松弛操作改成了a-u-b-e这种情况按理来说是要更新e的路程值但我们不需要额外处理因为这个算法会不停的遍历等遍历到边be的时候就会通过松弛操作更新路程值这一轮没遍历到那就下一轮。第二如果图中存在由权值为负的边组成的负权环Bellman-Ford算法也会失效所以是需要判断图中有没有负权环的。第三在没有负权环的情况下。如果顶点数为n那么Bellman-Ford算法最多只会遍历n轮也就是把所有的边遍历n-1次最后一次判断有没有负权环。每轮遍历可以保证至少选出一条边满足最短路径。原因比较抽象感兴趣的可以自行了解。第四Bellman-Ford算法虽然一开始也和Dijkstra算法一样是从起点开始松弛附近的边不断扩展但是由于遍历没有限制很快就能把每个顶点都更新一遍然后再不断缩短路径。它能够处理负权值的原因也在这里。如果后面有负权值的边可能会导致前面的路径连接这条边后反而变短但是Dijkstra算法只看附近的边没法预知哪里会有负权边也不会去处理已经选中的边和顶点所以碰到负权边会失效。而Bellman-Ford算法由于本身比较“吃苦耐劳”不停地遍历所有边所以能应对负权边当然代价就是效率比较低下。最后Bellman-Ford算法也有经过优化的版本SPFA。由于Bellman-Ford算法每轮遍历其实只需松弛那些被修改过路程值的顶点出发的边所以可以用一个队列存储这些顶点出队列时对从该顶点出发的边进行松弛并把修改过路程值的顶点入队列直到队列为空。具体可以看文末的代码里面的BellmanFord函数就是Bellman-Ford算法优化后的SPFA。多源最短路径Floyd-Warshall算法Floyd-Warshall算法也可以处理带有负权边的图其核心是动态规划。对于一个三维数组DD[ i ][ j ][ k ]表示从第 i 个顶点出发只经过前k个顶点中的若干个顶点到达第 j 个顶点的最短路径长度也就是前面说的路程值默认都为无穷大。D[ i ][ j ][ 0 ]则表示从顶点 i 直接连接到顶点 j 的边的权值。 将所有边的权值输入DD[ i ][ i ][ 0 ]设为0D[ 0 ][ j ][ k ]和D[ i ][ 0 ][ k ]没有意义前两个维度中的 i 和 j 的取值都是从1开始只有第三维的k才能取0但在动态规划的过程中k也是从1开始但是会用到k-1。为方便讲述下面将第 t 个顶点称作顶点 t 或者 t。状态转移方程的关键在于怎么从D[ i ][ j ][k-1]得到D[ i ][ j ][ k ]。假设顶点 i 到顶点 j 的最短路径经过顶点k那么 i 到 j 的最短路径长度是 i 到 k 的长度加 k 到 j 的长度即D[ i ][ j ][ k ]D[ i ][ k ][k-1]D[ k ][ j ][k-1]再假设没经过顶点k的情况那就和只经过前k-1个顶点中的若干个顶点没有区别D[ i ][ j ][ k ]D[ i ][ k ][ k-1 ]取二者中的较小者就是最终的状态转移方程D[ i ][ j ][ k ]min{D[ i ][ k ][ k-1 ]D[ k ][ j ][k-1]D[ i ][ k ][k-1]}对于任意的顶点 i 、jD[ i ][ j ][ 0 ]是 i 到 j 的边的权值。k虽然是数组D的第三维但是在循环中是最外层的循环因子。即循环的最外层为while(kn)所以在计算D[ i ][ j ][ k ]时对于任意的 s 、t, D[ s ][ t ][k-1]都是已经处理完成的最优路程值。故可以保证在动态规划的过程中上式右边的各项都是有意义的。其次我们还需要记录各顶点在最短路径中的前一个顶点由于起点是任意的所以需要用二维数组来记录。如我用的是parentparent[ s ][ d ]表示在起点为 s 的最短路径中顶点d的前一个顶点。在前面的转态转移方程中如果 i 到 j 有经过顶点k那么顶点 j 在以 i 为起点的最短路径中的前一个顶点应该是顶点 j 在以k为起点的最短路径中的前一个节点 也就是parent[ i ][ j ]parent[ k ][ j ]这是因为顶点k也不一定是直接连接到 j 的。如果没有经过第k个顶点那前一个顶点就没有变化。降维优化实际上为了节约空间Floyd-Warshall算法会通过在原来的空间上迭代可以将D降为二维。D[ i ][ j ]表示顶点 i 到顶点 j 的最短路径长度。与前面不同的是这里的顶点 i 就是指下标为 i 的顶点顶点 j 同理。初始化时D[ i ][ j ]是顶点 i 到顶点 j 的边的权值D[ i ][ i ]取0其它的取无穷大。不难发现在开始动态规划之前D就是邻接矩阵。接下来我们将在多轮动态规划中不断迭代让D[ i ][ j ]从边的权值变为最短路径长度。首先假设顶点 i 到 j 的最短路径要么经过顶点0要么直连由此进行动态规划。如果有顶点 i 到顶点 j 的最短路径有经过顶点0那么D[ i ][ j ]D[ i ][ 0 ]D[ 0 ][ j ]如果没有则D[ i ][ j ]没有变化所以状态转移方程为D[ i ][ j ]min{D[ i ][ j ] , D[ i ][ 0 ]D[ 0 ][ j ] }此时D中的路径就是有经过顶点集合{ 0 }中若干个顶点的最短路径也就是要么经过0要么没有。接下来假设D[ i ][ j ]是经过顶点集合 {012……k-1}中若干个顶点的最短路径长度k可以等于1我们要由此推广到包含顶点k的情况。不难得到状态转移方程D[ i ][ j ]min{D[ i ][ j ]D[ i ][ k ]D[ k ][ j ]}令k从0增加到编号最大的顶点n-1使用上面这个状态转移方程进行多轮动态规划就可以得到真正的最短路径。前一个顶点的记录和前面一样若有经过顶点k则parent[ i ][ j ]parent[ k ][ j ]如果没有就不变。我们可以发现其实整体的思路没有变化只是不再记录由k的值带来的变化而是通过不断的迭代节省空间。具体可以参考文末的代码。参考代码注意代码只经过了粗略的验证不能保证完全正确只提供大致的思路。头文件和Kruskal算法需要用到的并查集#includeiostream #includemap #includevector #includequeue using namespace std; class Unionfindset { public: Unionfindset(size_t n) : _ufs(n, -1) { } int Findroot(int x) {//找老大返回老大的编号 if (_ufs[x] 0) return x; else return _ufs[x] Findroot(_ufs[x]);//直接让下属连接老大提高找老大的效率 } void Union(int a, int b) {//交友、联合将a看作上司 int ar Findroot(a); int br Findroot(b); if (ar ! br) { _ufs[ar] _ufs[br];//算人数 _ufs[br] ar;//认老大 } } size_t Setsize(int x) {//返回x所在团体的大小 return -_ufs[Findroot(x)]; } size_t count() {//返回团体个数 size_t ans 0; for (auto e : _ufs) { if (e 0) ans; } return ans; } private: vectorint _ufs; };使用邻接矩阵实现的图//用邻接矩阵实现的图 namespace Matrix { templateclass V, class W, W MAX_W INT_MAX, bool Direction false//顶点类型权值类型无穷大是否为有向图 class Graph { typedef GraphV, W, MAX_W, Direction Self; public: Graph() default; Graph(const V* vertexs, size_t n) {//先存顶点边后面再加上 _vertexs vectorV(n, V()); for (int i 0; i n; i) { _vertexs[i] vertexs[i]; _vIndexMap[vertexs[i]] i; } _matrix vectorvectorW (n, vectorW(n, MAX_W)); for (int i 0; i n; i) { _matrix[i][i] 0; } } int GetVertexIndex(const V v) {//返回顶点对应下标 auto it _vIndexMap.find(v); if (it ! _vIndexMap.end()) { return it-second; } else { cout 该顶点不存在 endl; return -1; } } void _AddEdge(size_t srci, size_t dsti, const W w) {//用顶点下标添加边 _matrix[srci][dsti] w; if (!Direction) _matrix[dsti][srci] w; } void AddEdge(const V v1, const V v2, const W w) {//用顶点添加 int sr GetVertexIndex(v1); int ds GetVertexIndex(v2); if (sr -1 || ds -1) return; _AddEdge(sr, ds, w); } void BFS() { if (_vertexs.size() 0) return; queueint que; vectorbool hash(_vertexs.size(), false);//是否被访问过 int count 0;//遍历过的顶点数 while (count ! _vertexs.size()) { for (int i 0; i hash.size(); i) {//找一个没遍历过的入队 if (!hash[i]) { que.push(i); hash[i] true; count; break; } } while (!que.empty()) { cout _vertexs[que.front()] ; for (int j 0; j _matrix.size(); j) { if (_matrix[que.front()][j] ! MAX_W !hash[j]) { hash[j] true; que.push(j); count; } } que.pop(); } cout endl; } } void _DFS_Func(vectorbool hash, int set) {//DFS核心递归函数 if (hash[set]) return; cout _vertexs[set] ; hash[set] true; for (int j 0; j _matrix.size(); j) { if (_matrix[set][j] ! MAX_W) _DFS_Func(hash,j); } } void DFS() {//封装 vectorbool hash(_vertexs.size(), false);//是否被访问过 while (1) { int i; for (i 0; i hash.size(); i) {//检查遍历完了没 if (!hash[i]) break; } if (i ! hash.size()) _DFS_Func(hash, i); else break; cout endl; } } struct Edge {//用于方便构造最小生成树 W _w;//权值 int _src;//该边出发的顶点的值 int _dst;//该边指向的顶点的值 Edge(W w) :_dst(-1), _src(-1), _w(w) {} bool operator(const Edge b) const {//用于堆中的比较 return _w b._w; } }; W Kruskal(Self mintree) {//返回权值总和mintree用于存储最小生成树 if (Direction) { cout 该图为有向图 endl; return W(); } mintree._vertexs _vertexs;//顶点都一样边后面加 //由于没有调用构造函数邻接矩阵要手动初始化 mintree._matrix.resize(_vertexs.size(), vectorW(_vertexs.size(), MAX_W)); priority_queueEdge, vectorEdge, greaterEdge edgeque;//小根堆存储所有边 for (int i 0; i _matrix.size(); i) { for (int j 0; j i; j) { if (_matrix[i][j] ! MAX_W){ Edge temp(_matrix[i][j]); temp._src i; temp._dst j; edgeque.push(temp); } } } Unionfindset ufs(_vertexs.size());//并查集 int count 1;//用于判断是不是生成树 W sumW();//计算权值之和 while (count!_vertexs.size() !edgeque.empty()) { Edge temp edgeque.top(); edgeque.pop(); if (ufs.Findroot(temp._src) ! ufs.Findroot(temp._dst)) {//用并查集判断是否构成环 ufs.Union(temp._src, temp._dst); mintree._AddEdge(temp._src, temp._dst, temp._w); sum temp._w; count; } } if (count _vertexs.size()) return sum;//判断是不是生成树 else return W(); } W Prim(Self mintree, V src) {//st是起点 if (Direction) { cout 该图为有向图 endl; return W(); } mintree._vertexs _vertexs;//顶点都一样边后面加 //由于没有调用构造函数邻接矩阵要手动初始化 mintree._matrix.resize(_vertexs.size(), vectorW(_vertexs.size(), MAX_W)); size_t st _vIndexMap[src]; vectorbool hash(_vertexs.size(), true);//记录未连接的顶点 hash[st] false; priority_queueEdge,vectorEdge,greaterEdge edgeque;//小根堆存储附近的所有边 for (int i st; i _matrix[st].size(); i) { if (_matrix[st][i] ! MAX_W i!st) { Edge temp(_matrix[st][i]); temp._src st; temp._dst i; edgeque.push(temp); } } int count 1; W sum W(); while (count ! _vertexs.size() !edgeque.empty()) { Edge temp edgeque.top(); edgeque.pop(); if (hash[temp._dst]) { hash[temp._dst] false; mintree._AddEdge(temp._src, temp._dst, temp._w); count; sum temp._w; for (int j 0; j _matrix[temp._dst].size(); j) {//连接的顶点的所有边加入堆 if (_matrix[temp._dst][j] ! MAX_W hash[j]) {//hash[j]防止连到旧顶点和同一个顶点优化一点效率 Edge t(_matrix[temp._dst][j]); t._src temp._dst; t._dst j; edgeque.push(t); } } } } if (count _vertexs.size()) return sum;//判断是不是生成树 else return W(); } //包含从起点出发到所有顶点的最短路径的信息 void Dijkstra(V srci, vectorW path, vectorint parent) { size_t N _vertexs.size(); int sr _vIndexMap[srci]; path.resize(N, MAX_W);//到各个顶点的最短路径的长度 parent.resize(N, -1);//各个顶点的在各自最短路径中的上一个节点下面简称父节点不断回溯即可确定其最短路径值为-1表示父节点是自己 vectorbool hash(N, false);//true表示该顶点属于找到最短路径的S反之则属于未处理的Q priority_queueEdge, vectorEdge, greaterEdge edgeque;//小根堆存储附近的所有边 path[sr] W(); Edge t(0); t._dst sr; t._src sr; edgeque.push(t); while (!edgeque.empty()) { int cur edgeque.top()._dst;//取的是顶点而不是边 //判断一下从这条边到达是不是最短路径是的话要更新路径长度和父节点 if (path[edgeque.top()._src] edgeque.top()._w path[edgeque.top()._dst]) { path[edgeque.top()._dst] path[edgeque.top()._src] edgeque.top()._w; parent[edgeque.top()._dst] edgeque.top()._src; } edgeque.pop(); if (hash[cur]) continue; hash[cur] true; for (int j 0; j N; j) { if (hash[j] || _matrix[cur][j] MAX_W) continue; Edge temp(_matrix[cur][j]); temp._src cur; temp._dst j; edgeque.push(temp); if (path[cur] _matrix[cur][j] path[j]) {//松弛父节点会在取出边时更新 path[j] path[cur] _matrix[cur][j]; } } } } bool BellmanFord(V srci, vectorW path, vectorint parent) { size_t N _vertexs.size(); int sr _vIndexMap[srci]; path.resize(N, MAX_W);//到各个顶点的最短路径的长度 parent.resize(N, -1);//各个顶点的在各自最短路径中的上一个节点下面简称父节点不断回溯即可确定其最短路径值为-1表示父节点是自己 vectorint count(N, 0);//记录每个顶点遍历次数防止负权环带来的死循环 queueint verque;//顶点队列 vectorboolhash(N, false);//记录顶点是否在队列里防重复 path[sr] 0; verque.push(sr); hash[sr] true; while (!verque.empty()) { int temp verque.front(); verque.pop(); hash[temp] false; count[temp]; if (count[temp] N) return false; for (int j 0; j N; j) { if (_matrix[temp][j]!MAX_W path[j] _matrix[temp][j] path[temp]) { path[j] _matrix[temp][j] path[temp]; parent[j] temp; if (!hash[j]) { verque.push(j);; hash[j] true; } } } } return true; } void FloydWarShall(vectorvectorW path, vectorvectorint parent) {//path就是D size_t N _vertexs.size(); path _matrix;//初始时就是邻接矩阵 parent.resize(N, vectorint(N, -1)); for (int i 0; i N; i) { for (int j 0; j N; j) { if (_matrix[i][j] ! MAX_W i ! j) parent[i][j] i;//父节点也要初始化 } } for (int k 0; k N; k) { for (int i 0; i N; i) { for (int j 0; j N; j) { if (path[i][k] ! MAX_W path[k][j] ! MAX_W i ! j path[i][j] path[i][k] path[k][j]) {//有经过顶点k path[i][j] path[i][k] path[k][j]; parent[i][j] parent[k][j]; } } } } } void Print() {//输出图的内容 for (auto i : _vertexs) {//打印顶点与下标关系 cout i ; } cout endl; for (int i 0; i _vertexs.size(); i) cout i ; cout endl endl; for (auto i : _matrix) {//打印邻接矩阵 for (auto j : i) { if (j ! MAX_W) cout j ; else cout # ; } cout endl; } cout endl; int sup; for (int i 0; i _matrix.size(); i) {//打印所有的边 if (Direction) sup _matrix[i].size(); else sup i; for (int j 0; j sup; j) { if (_matrix[i][j] ! MAX_W Direction) cout _vertexs[i] -- _matrix[i][j] -- _vertexs[j] endl; else if (_matrix[i][j] ! MAX_W) cout _vertexs[i] -- _matrix[i][j] -- _vertexs[j] endl; } } } void PrinrtShotPath(V srci, vectorW dist, vectorint parent) {//打印以srci为起点的所有最短路径 int sr _vIndexMap[srci]; for (int i 0; i parent.size(); i) { if (i sr) continue; vectorint path; int cur i; while (cur ! -1) { path.push_back(cur); cur parent[cur]; } cout 最短路径: endl; for (int i path.size() - 1; i 0; i--) { cout _vertexs[path[i]] -; } cout endl; cout 长度 dist[i] endl endl; } } private: vectorV _vertexs;//顶点 mapV, int _vIndexMap;//映射顶点-编号 vectorvectorW _matrix;//邻接矩阵 }; }使用邻接表实现的图//用邻接表实现的图 namespace Link_Table { templateclass W struct Edge { W _w;//权值 int _src;//该边出发的顶点的值 int _dst;//该边指向的顶点的值 EdgeW* _next; Edge(W w) :_dst(-1), _src(-1), _w(w), _next(nullptr) { } bool operator(const Edge b) const {//用于堆中的比较 return _w b._w; } }; templateclass V, class W, W MAX_W INT_MAX, bool Direction false//顶点类型权值类型无穷大是否为有向图 class Graph { typedef EdgeW Edge; typedef GraphV, W, MAX_W, Direction Self; public: Graph() default; Graph(const V* vertexs, size_t n) {//先存顶点边后面再加上 _vertexs vectorV(n, V()); for (int i 0; i n; i) { _vertexs[i] vertexs[i]; _vIndexMap[vertexs[i]] i; } _LinkTable.resize(n, nullptr); } int GetVertexIndex(const V v) {//返回顶点对应下标 auto it _vIndexMap.find(v); if (it ! _vIndexMap.end()) { return it-second; } else { cout 该顶点不存在 endl; return -1; } } void _AddEdge(size_t sr, size_t ds, const W w) {//用顶点下标添加边 if (sr _vertexs.size() || ds _vertexs.size() || _LinkTable[sr] _LinkTable[sr]-_dst ds)//顶点不存在或者边已经有了 return; Edge* temp new Edge(w); temp-_src sr; temp-_dst ds; //头插也只能头插 temp-_next _LinkTable[sr]; _LinkTable[sr] temp; if (!Direction) {//无向图要再加一条反过来的 _AddEdge(ds, sr, w); } } void AddEdge(const V v1, const V v2, const W w) {//用顶点添加边 int sr GetVertexIndex(v1); int ds GetVertexIndex(v2); if (sr -1 || ds -1) return; _AddEdge(sr, ds, w); } void BFS() { if (_vertexs.size() 0) return; queueint que; vectorbool hash(_vertexs.size(), false);//是否被访问过 int count 0;//遍历过的顶点数 while (count ! _vertexs.size()) { for (int i 0; i hash.size(); i) {//找一个没遍历过的入队 if (!hash[i]) { que.push(i); hash[i] true; count; break; } } while (!que.empty()) { cout _vertexs[que.front()] ; Edge* cur _LinkTable[que.front()]; while (cur) { hash[cur-_dst] true; count; que.push(cur-dst); cur cur-_next; } que.pop(); } cout endl; } } void _DFS_Func(vectorbool hash, int set) {//DFS核心递归函数 if (hash[set]) return; cout _vertexs[set] ;//遍历当前顶点 hash[set] true; Edge* cur _LinkTable[set];//寻找下一个顶点 while (cur) { _DFS_Func(hash, cur-_dst); cur cur-_next; } } void DFS() {//封装 vectorbool hash(_vertexs.size(), false);//是否被访问过 while (1) { int i; for (i 0; i hash.size(); i) {//检查遍历完了没 if (!hash[i]) break; } if (i ! hash.size()) _DFS_Func(hash, i);//开始递归 else break; cout endl; } } W Kruskal(Self mintree) {//返回权值总和mintree用于存储最小生成树 if (Direction) { cout 该图为有向图 endl; return W(); } mintree._vertexs _vertexs;//顶点都一样边后面加 //由于没有调用构造函数邻接表要手动初始化 mintree._LinkTable.resize(_vertexs.size(), nullptr); priority_queueEdge, vectorEdge, greaterEdge edgeque;//小根堆存储所有边 for (int i 0; i _LinkTable.size(); i) { Edge* cur _LinkTable[i]; while (cur) { edgeque.push(*cur); cur cur-_next; } } Unionfindset ufs(_vertexs.size());//并查集 int count 1;//用于判断是不是生成树 W sum W();//计算权值之和 while (count ! _vertexs.size() !edgeque.empty()) { Edge temp edgeque.top(); edgeque.pop(); if (ufs.Findroot(temp._src) ! ufs.Findroot(temp._dst)) {//用并查集判断是否构成环 ufs.Union(temp._src, temp._dst); mintree._AddEdge(temp._src, temp._dst, temp._w); sum temp._w; count; } } if (count _vertexs.size()) return sum;//判断是不是生成树 else return W(); } W Prim(Self mintree, V src) {//src是起点 if (Direction) { cout 该图为有向图 endl; return W(); } mintree._vertexs _vertexs;//顶点都一样边后面加 //由于没有调用构造函数邻接表要手动初始化 mintree._LinkTable.resize(_vertexs.size(), nullptr); size_t st _vIndexMap[src]; vectorbool hash(_vertexs.size(), true);//记录未连接的顶点 hash[st] false; priority_queueEdge, vectorEdge, greaterEdge edgeque;//小根堆存储附近的所有边 Edge* cur _LinkTable[st]; while (cur) { edgeque.push(*cur); cur cur-_next; } int count 1; W sum W(); while (count ! _vertexs.size() !edgeque.empty()) { Edge temp edgeque.top(); edgeque.pop(); if (hash[temp._dst]) { hash[temp._dst] false; mintree._AddEdge(temp._src, temp._dst, temp._w); count; sum temp._w; Edge* cur _LinkTable[temp._dst]; while (cur) { if (hash[cur-_dst]) edgeque.push(*cur); cur cur-_next; } } } if (count _vertexs.size()) return sum;//判断是不是生成树 else return W(); } //包含从起点出发到所有顶点的最短路径的信息 void Dijkstra(V srci, vectorW path, vectorint parent) { size_t N _vertexs.size(); int sr _vIndexMap[srci]; path.resize(N, MAX_W);//到各个顶点的最短路径的长度 parent.resize(N, -1);//各个顶点的在各自最短路径中的上一个节点下面简称父节点不断回溯即可确定其最短路径值为-1表示父节点是自己 vectorbool hash(N, false);//true表示该顶点属于找到最短路径的S反之则属于未处理的Q priority_queueEdge, vectorEdge, greaterEdge edgeque;//小根堆存储附近的所有边 path[sr] W(); Edge t(0); t._dst sr; t._src sr; edgeque.push(t); while (!edgeque.empty()) { int cur edgeque.top()._dst;//取的是顶点而不是边 //判断一下从这条边到达是不是最短路径是的话要更新路径长度和父节点 if (path[edgeque.top()._src] edgeque.top()._w path[edgeque.top()._dst]) { path[edgeque.top()._dst] path[edgeque.top()._src] edgeque.top()._w; parent[edgeque.top()._dst] edgeque.top()._src; } edgeque.pop(); if (hash[cur]) continue; hash[cur] true; Edge* ep _LinkTable[cur];//附近的边加入堆中 while (ep) { if (!hash[ep-_dst]) { edgeque.push(*ep); if (path[cur] ep-_w path[ep-_dst]) {//松弛父节点会在取出边时更新 path[ep-_dst] path[cur] ep-_w; } } ep ep-_next; } } } bool BellmanFord(V srci, vectorW path, vectorint parent) { size_t N _vertexs.size(); int sr _vIndexMap[srci]; path.resize(N, MAX_W);//到各个顶点的最短路径的长度 parent.resize(N, -1);//各个顶点的在各自最短路径中的上一个节点下面简称父节点不断回溯即可确定其最短路径值为-1表示父节点是自己 vectorint count(N, 0);//记录每个顶点遍历次数防止负权环带来的死循环 queueint verque;//顶点队列 vectorboolhash(N, false);//记录顶点是否在队列里防重复 path[sr] 0; verque.push(sr); hash[sr] true; while (!verque.empty()) { int temp verque.front(); verque.pop(); hash[temp] false; count[temp]; if (count[temp] N) return false; Edge* cur _LinkTable[temp]; while (cur) { if (path[cur-_dst] cur-_w path[cur-_src]) {//松弛 path[cur-_dst] cur-_w path[cur-_src]; parent[cur-_dst] cur-_src; if (!hash[cur-_dst]) { verque.push(cur-_dst); hash[cur-_dst] true; } } cur cur-_next; } } return true; } void FloydWarShall(vectorvectorW path, vectorvectorint parent) {//path就是D size_t N _vertexs.size(); path.resize(N, vectorW(N, MAX_W));//初始化 parent.resize(N, vectorint(N, -1)); for (int i 0; i N; i) { Edge* cur _LinkTable[i]; while (cur) { path[cur-_src][cur-_dst] cur-_w; parent[cur-_src][cur-_dst] cur-_src;//父节点也要初始化 cur cur-_next; } path[i][i] W(); } for (int k 0; k N; k) { for (int i 0; i N; i) { for (int j 0; j N; j) { if (path[i][k] ! MAX_W path[k][j] ! MAX_W i ! j path[i][j] path[i][k] path[k][j]) {//有经过顶点k path[i][j] path[i][k] path[k][j]; parent[i][j] parent[k][j]; } } } } } void Print() {//输出图的内容 for (auto i : _vertexs) {//打印顶点与下标关系 cout i ; } cout endl; for (int i 0; i _vertexs.size(); i) cout i ; cout endl endl; for (int i 0; i _LinkTable.size(); i) {//打印邻接表 if (_LinkTable[i]) { cout _vertexs[i] ( i ): ; Edge* cur _LinkTable[i]; while (cur) { cout _vertexs[cur-_dst] ( cur-_dst ) --cur-_w-- ; cur cur-_next; } cout nullptr endl; } else cout _vertexs[i] ( i ): nullptrendl; } } void PrinrtShotPath(V srci, vectorW dist, vectorint parent) {//打印以srci为起点的所有最短路径 int sr _vIndexMap[srci]; for(int i0;iparent.size();i) { if (i sr) continue; vectorint path; int cur i; while (cur ! -1) { path.push_back(cur); cur parent[cur]; } cout 最短路径: endl; for (int i path.size() - 1; i 0; i--) { cout _vertexs[path[i]] -; } cout endl; cout 长度 dist[i] endlendl; } } private: vectorV _vertexs;//顶点 mapV, int _vIndexMap;//映射顶点-编号 vectorEdge* _LinkTable;//邻接表出边表 }; }