目录
图的基本概念
图的存储和遍历
邻接矩阵
邻接表
图的遍历
构造最小生成树
Kruskal算法
Prim算法
最短路径问题
单源最短路径
Dijkstra算法
Bellman-Ford算法
多源最短路径
Floyd-Warshall算法
参考代码
图的基本概念
图是由顶点集合及顶点间的关系（边）组成的一种数据结构，用G = (V， E)表示。其中V是顶点的集合，顶点的个数不能为0；E是顶点间关系的集合，也就是边的集合，它的个数可以为0。简单来说，图就是由有限个顶点和有限条边组成的。
图中第i个顶点记作vi，（i是下标），编号没有要求，可以自行给顶点和边编号。图中第k条边记作ek（k是下标）。边有双向和单向之分，ek=<vi,vj>表示ek是顶点vi到顶点vj的一条有向边，类似单行道，在这条边上只能从vi走到vj，如果是ek=（vi,vj）则表示ek是顶点vi和顶点vj的一条无向边，没有特定的方向（其实就是双向的边）。其中<vi,vj>和（vi,vj）也叫顶点对，分为有序和无序，<vi,vj>是有序的，也就是有向的，所以<vi,vj>和<vj,vi>不同，无序的顶点对（vi，vj）则和（vj,vi）相同。一个图中只能有一种边，要么都是无向边，要么都是有向边。如下，左边的图只有有向边，叫做有向图，右边的图则是只有无向边的无向图。
如果图中所有能存在的边都已经存在，再画一条边就必定会跟其中一条边重复的图就是完全图。有向的叫有向完全图（下图左边），如果有n个顶点就有有n*(n-1)条边，无向的叫无向完全图(下图右边)，n个顶点有 n*(n-1)/2条边。
在无向图中G=（V，E）中，若(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）是边附带的数据信息，对于不带权的图，一条路径的路径长度是指该路径上的边的条数；对于带权的图（如下），一条路径的路径长度是指该路径上各个边权值的总和。
若路径上各顶点v1，v2，v3，…，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->d，d的前一个顶点就是c。我们要看d的最短路径，就通过数组找到了c，现在只需要知道c的最短路径，所以又通过数组找到了b，于是又变成了要看b的最短路径，一直找到起点a就得到了最短路径。
那么如何在S附近找到这条满足最短路径的边呢？和prim算法有些相似。首先一开始S中只有一个作为起点的顶点，从它出发的边中最短的那条肯定满足最短路径，我们将其出发的边都放入小根堆，找到那条最短的边，将其连接的顶点（暂时命名为u）加入S。接着将从u出发的边都放入小根堆。但这时堆中最短的边就不一定满足最短路径了，如下，S附近最短的边为60，但蓝色顶点的最短路径应该是从顶点出发的100。
为此，在开始找最短路径前，我们先将起点到所有顶点的路径权值之和（下称路程值）都看作无穷大，起点到自身的则看作0或者权值W的缺省值，每次向S中加入顶点时，对从其出发的所有的边（不包括指向S中顶点的边）进行松弛操作，比如我们要松弛边<u，v>，就比较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的路程值，但我们不需要额外处理，因为这个算法会不停的遍历，等遍历到边<b，e>的时候就会通过松弛操作更新路程值，这一轮没遍历到那就下一轮。
第二，如果图中存在由权值为负的边组成的负权环，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算法也可以处理带有负权边的图，其核心是动态规划。对于一个三维数组D，D[ i ][ j ][ k ]表示从第 i 个顶点出发，只经过前k个顶点中的若干个顶点，到达第 j 个顶点的最短路径长度，也就是前面说的路程值，默认都为无穷大。D[ i ][ j ][ 0 ]则表示从顶点 i 直接连接到顶点 j 的边的权值。 将所有边的权值输入D，D[ i ][ i ][ 0 ]设为0，D[ 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 、j，D[ i ][ j ][ 0 ]是 i 到 j 的边的权值。
k虽然是数组D的第三维，但是在循环中是最外层的循环因子。即循环的最外层为while(k<=n)，所以在计算D[ i ][ j ][ k ]时，对于任意的 s 、t, D[ s ][ t ][k-1]都是已经处理完成的最优路程值。
故可以保证在动态规划的过程中，上式右边的各项都是有意义的。
其次，我们还需要记录各顶点在最短路径中的前一个顶点，由于起点是任意的，所以需要用二维数组来记录。如我用的是parent，parent[ 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 ]是经过顶点集合 {0，1，2，……，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算法需要用到的并查集
#include<iostream> #include<map> #include<vector> #include<queue> 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: vector<int> _ufs; };使用邻接矩阵实现的图
//用邻接矩阵实现的图 namespace Matrix { template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>//顶点类型，权值类型，无穷大，是否为有向图 class Graph { typedef Graph<V, W, MAX_W, Direction> Self; public: Graph() = default; Graph(const V* vertexs, size_t n) {//先存顶点，边后面再加上 _vertexs = vector<V>(n, V()); for (int i = 0; i < n; i++) { _vertexs[i] = vertexs[i]; _vIndexMap[vertexs[i]] = i; } _matrix = vector<vector<W> >(n, vector<W>(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; queue<int> que; vector<bool> 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(vector<bool>& 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() {//封装 vector<bool> 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(), vector<W>(_vertexs.size(), MAX_W)); priority_queue<Edge, vector<Edge>, greater<Edge> > 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 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) {//st是起点 if (Direction) { cout << "该图为有向图" << endl; return W(); } mintree._vertexs = _vertexs;//顶点都一样，边后面加 //由于没有调用构造函数，邻接矩阵要手动初始化 mintree._matrix.resize(_vertexs.size(), vector<W>(_vertexs.size(), MAX_W)); size_t st = _vIndexMap[src]; vector<bool> hash(_vertexs.size(), true);//记录未连接的顶点 hash[st] = false; priority_queue<Edge,vector<Edge>,greater<Edge> > 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, vector<W>& path, vector<int>& parent) { size_t N = _vertexs.size(); int sr = _vIndexMap[srci]; path.resize(N, MAX_W);//到各个顶点的最短路径的长度 parent.resize(N, -1);//各个顶点的在各自最短路径中的上一个节点，下面简称父节点，不断回溯即可确定其最短路径，值为-1表示父节点是自己 vector<bool> hash(N, false);//true表示该顶点属于找到最短路径的S，反之则属于未处理的Q priority_queue<Edge, vector<Edge>, greater<Edge> > 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, vector<W>& path, vector<int>& parent) { size_t N = _vertexs.size(); int sr = _vIndexMap[srci]; path.resize(N, MAX_W);//到各个顶点的最短路径的长度 parent.resize(N, -1);//各个顶点的在各自最短路径中的上一个节点，下面简称父节点，不断回溯即可确定其最短路径，值为-1表示父节点是自己 vector<int> count(N, 0);//记录每个顶点遍历次数，防止负权环带来的死循环 queue<int> verque;//顶点队列 vector<bool>hash(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(vector<vector<W>>& path, vector<vector<int>>& parent) {//path就是D size_t N = _vertexs.size(); path = _matrix;//初始时就是邻接矩阵 parent.resize(N, vector<int>(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, vector<W>& dist, vector<int>& parent) {//打印以srci为起点的所有最短路径 int sr = _vIndexMap[srci]; for (int i = 0; i < parent.size(); i++) { if (i == sr) continue; vector<int> 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: vector<V> _vertexs;//顶点 map<V, int> _vIndexMap;//映射：顶点->编号 vector<vector<W> > _matrix;//邻接矩阵 }; }使用邻接表实现的图
//用邻接表实现的图 namespace Link_Table { template<class W> struct Edge { W _w;//权值 int _src;//该边出发的顶点的值 int _dst;//该边指向的顶点的值 Edge<W>* _next; Edge(W w) :_dst(-1), _src(-1), _w(w), _next(nullptr) { } bool operator>(const Edge& b) const {//用于堆中的比较 return _w > b._w; } }; template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>//顶点类型，权值类型，无穷大，是否为有向图 class Graph { typedef Edge<W> Edge; typedef Graph<V, W, MAX_W, Direction> Self; public: Graph() = default; Graph(const V* vertexs, size_t n) {//先存顶点，边后面再加上 _vertexs = vector<V>(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; queue<int> que; vector<bool> 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(vector<bool>& 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() {//封装 vector<bool> 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_queue<Edge, vector<Edge>, greater<Edge> > 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]; vector<bool> hash(_vertexs.size(), true);//记录未连接的顶点 hash[st] = false; priority_queue<Edge, vector<Edge>, greater<Edge> > 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, vector<W>& path, vector<int>& parent) { size_t N = _vertexs.size(); int sr = _vIndexMap[srci]; path.resize(N, MAX_W);//到各个顶点的最短路径的长度 parent.resize(N, -1);//各个顶点的在各自最短路径中的上一个节点，下面简称父节点，不断回溯即可确定其最短路径，值为-1表示父节点是自己 vector<bool> hash(N, false);//true表示该顶点属于找到最短路径的S，反之则属于未处理的Q priority_queue<Edge, vector<Edge>, greater<Edge> > 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, vector<W>& path, vector<int>& parent) { size_t N = _vertexs.size(); int sr = _vIndexMap[srci]; path.resize(N, MAX_W);//到各个顶点的最短路径的长度 parent.resize(N, -1);//各个顶点的在各自最短路径中的上一个节点，下面简称父节点，不断回溯即可确定其最短路径，值为-1表示父节点是自己 vector<int> count(N, 0);//记录每个顶点遍历次数，防止负权环带来的死循环 queue<int> verque;//顶点队列 vector<bool>hash(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(vector<vector<W>>& path, vector<vector<int>>& parent) {//path就是D size_t N = _vertexs.size(); path.resize(N, vector<W>(N, MAX_W));//初始化 parent.resize(N, vector<int>(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 << "): nullptr"<<endl; } } void PrinrtShotPath(V srci, vector<W>& dist, vector<int>& parent) {//打印以srci为起点的所有最短路径 int sr = _vIndexMap[srci]; for(int i=0;i<parent.size();i++) { if (i == sr) continue; vector<int> 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: vector<V> _vertexs;//顶点 map<V, int> _vIndexMap;//映射：顶点->编号 vector<Edge*> _LinkTable;//邻接表（出边表） }; }
