一、并查集
1.并查集原理
在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个 单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一 个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find set)。
- 像堆类似，用下标表示关系
- 双亲表示法
补充：
表示：初始状态给的是-1，表示10颗树。
从上图可以看出：编号6,7,8同学属于0号小分队，该小分队中有4人(包含队长0)；编号为4和9的同 学属于1号小分队，该小分队有3人(包含队长1)，编号为3和5的同学属于2号小分队，该小分队有3 个人(包含队长1)。
特点：
- 一个位置值是负数，那他就是树的根，这个负数的绝对值就是这棵树数据个数
- 一个位置的值是正数，那他就是双亲的下标
仔细观察数组中内融化，可以得出以下结论：
- 数组的下标对应集合中元素的编号
- 数组中如果为负数，负号代表根，数字代表该集合中元素个数
- 数组中如果为非负数，代表该元素双亲在数组中的下标
在公司工作一段时间后，西安小分队中8号同学与成都小分队1号同学奇迹般的走到了一起，两个小圈子的学生相互介绍，最后成为了一个小圈子：
现在0集合有7个人，2集合有3个人，总共两个朋友圈。
通过以上例子可知，并查集一般可以解决一下问题：
1. 查找元素属于哪个集合
沿着数组表示树形关系以上一直找到根(即：树中中元素为负数的位置)
2. 查看两个元素是否属于同一个集合
沿着数组表示的树形关系往上一直找到树的根，如果根相同表明在同一个集合，否则不在
3. 将两个集合归并成一个集合
将两个集合中的元素合并 将一个集合名称改成另一个集合的名称
4. 集合的个数
遍历数组，数组中元素为负数的个数即为集合的个数。
2.并查集实现
class UnionFindSet { public: UnionFindSet(size_t n) :_ufs(n, -1) {} //合并 void Union(int x1, int x2) { int root1 = FindRoot(x1); int root2 = FindRoot(x2); //如果本身就在一个集合，就没必要合并 if (root1 == root2) return; //数据量小的往大的合并 if (abs(_ufs[root1]) > abs(_ufs[root2])) { swap(root1, root2); } _ufs[root1] += _ufs[root2]; _ufs[root2] = root1; } //找根 int FindRoot(int x) { int root = x; while (_ufs[root] >= 0) { root = _ufs[root]; } //路径压缩 while (_ufs[x] >= 0) { int parent = _ufs[x]; _ufs[x] = root; x = parent; } return root; } //判断x1和x2是否在同一个集合 bool InSet(int x1 , int x2) { return FindRoot(x1) == FindRoot(x2); } //集合数 size_t SetSize() { size_t size = 0; for (int i = 0; i < _ufs.size(); i++) { if (_ufs[i] < 0) { size++; } } return size; } private: vector<int> _ufs; };3.并查集应用
3.1 省份数量leetcode
116. 省份数量leetcode
代码实现如下(法一：并查集)：
class UnionFindSet { public: UnionFindSet(size_t n) :_ufs(n, -1) {} //合并 void Union(int x1, int x2) { int root1 = FindRoot(x1); int root2 = FindRoot(x2); //如果本身就在一个集合，就没必要合并 if (root1 == root2) return; if (root1 > root2) { swap(root1, root2); } _ufs[root1] += _ufs[root2]; _ufs[root2] = root1; } //找根 int FindRoot(int x) { int parent = x; while (_ufs[parent] >= 0) { parent = _ufs[parent]; } return parent; } //判断x1和x2是否在同一个集合 bool InSet(int x1 , int x2) { return FindRoot(x1) == FindRoot(x2); } //集合数 size_t SetSize() { size_t size = 0; for (int i = 0; i < _ufs.size(); i++) { if (_ufs[i] < 0) { size++; } } return size; } private: vector<int> _ufs; }; class Solution { public: int findCircleNum(vector<vector<int>>& isConnected) { UnionFindSet ufs(isConnected.size()); for(size_t i = 0 ; i < isConnected.size();i++) { for(int j = 0;j<isConnected[i].size();j++) { if(isConnected[i][j] == 1) { ufs.Union(i,j); } } } return ufs.SetSize(); } };代码实现二：
class Solution { public: int findCircleNum(vector<vector<int>>& isConnected) { vector<int> ufs(isConnected.size(),-1); auto findRoot = [&ufs](int x) { while(ufs[x] >= 0) x = ufs[x]; return x; }; for(int i = 0;i<isConnected.size();i++) { for(int j = 0;j<isConnected[i].size();j++) { if(isConnected[i][j] == 1) { //合并集合 int root1 = findRoot(i); int root2 = findRoot(j); if(root1 != root2) { ufs[root1] += ufs[root2]; ufs[root2] = root1; } } } } int n = 0; for(auto e:ufs) { if(e < 0) n++; } return n; } };3.2 等式方程的可满足性leetcode
990. 等式方程的可满足性 - 力扣（LeetCode）
代码实现（如下）
class Solution { public: bool equationsPossible(vector<string>& equations) { vector<int> ufs(26,-1); auto finRoot = [&ufs](int x) { while(ufs[x] >= 0) x = ufs[x]; return x; }; //第一遍，先把相等的值加到一个集合中 for(auto& str : equations) { if(str[1] == '=') { int root1 = finRoot(str[0] - 'a'); int root2 = finRoot(str[3] - 'a'); if(root1 != root2) { ufs[root1] += ufs[root2]; ufs[root2] = root1; } } } //第二遍，不相等的在不在一个集合，在就相悖了 //返回false for(auto& str : equations) { if(str[1] == '!') { int root1 = finRoot(str[0] - 'a'); int root2 = finRoot(str[3] - 'a'); if(root1 == root2) { return false; } } } return true; } };二、图
1. 图的基本概念
图是由顶点集合及顶点间的关系组成的一种数据结构：G = (V， E)，其中：
补充：
G：graph图
V：vertex顶点
E：edge边
顶点集合：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个顶点记作。两个顶点
和
相关联称作顶点
和顶点
之间 有一条边，图中的第k条边记作ek，
或
。
有向图和无向图：
- 在有向图中，顶点对<x,y>是有序的，顶点对<x,y>称为顶点x到顶点y的一条边(弧)，<x,y>和<y,z>是两条不同的边，比如下图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条边，即任意两个顶点之间有且仅有一条边， 则称此图为无向完全图，比如上图G1；
- 在n个顶点的有向图中，若有n * (n-1)条边，即任意两个顶点之间有且仅有方向相反的边，则称此图为有向完全图，比如上图G4。
邻接顶点：
- 在无向图中G中，若(u, v)是E(G)中的一条边，则称u和v互为邻接顶点，并称边(u,v)依附于顶点u和v；
- 在有向图G中，若<u,v>是E(G)中的一条边，则称顶点u邻接到v，顶点v邻接自顶点u，并称边与顶点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条边。
2. 图的存储结构
因为图中既有节点，又有边(节点与节点之间的关系)，因此，在图的存储中，只需要保存：节点和 边关系即可。
2.1 邻接矩阵
因为节点与节点之间的关系就是连通与否，即为0或者1，因此邻接矩阵(二维数组)即是：先用一个数组将定点保存，然后采用矩阵来表示节点与节点之间的关系。
无向图的邻接矩阵是对称矩阵。
注意：
- 无向图的邻接矩阵是对称的，第 i 行(列)元素之和，就是顶点 i 的度。
有向图的邻接矩阵则不一 定是对称的，第 i 行(列)元素之后就是顶点 i 的出(入)度。- 如果边带有权值，并且两个节点之间是连通的，上图中的边的关系就用权值代替，如果两个顶点不通，则使用无穷大代替。
- 用邻接矩阵存储图的要点是能够快速知道两个顶点是否连通，缺陷是如果顶点比较多，边比较少时，矩阵中存储了大量的0成为系数矩阵，比较浪费空间，并且要求两个节点之间的路径不是很好求。
邻接矩阵的优点:
- 邻接矩阵存储方式非常适合稠密图。
- 邻接矩阵O(1)判断两个顶点的连接关系，并取到权值。
邻接矩阵的缺点：
- 相对而言不适合用来查找一个顶点连接的所有边。——O(N)
代码实现：
namespace matrix { //vertex：边 weight：权值 false表示无向图，true表示有向图 template<class V, class W, W MAX_W = INT_MAX , bool Direction = false> class Graph { public: //图的创建 //1, IO输入 ---不方便测试，oj中更适合 //2，图结构关系写到文件，读取文件 //3，手动添加边 Graph(const V* a, size_t n) { _vertexs.reserve(n); for (size_t i = 0; i < n; i++) { _vertexs.push_back(a[i]); _indexMap[a[i]] = i; } _matrix.resize(n); for (int i = 0; i < _matrix.size(); i++) { _matrix[i].resize(n, MAX_W); } } size_t GetVertexIndex(const V& v) { auto it = _indexMap.find(v); if (it != _indexMap.end()) { return it->second; } else { assert(false); return -1; } } void AddEdge(const V& src, const V& dst, const W& w) { size_t srci = GetVertexIndex(src); size_t dsti = GetVertexIndex(dst); _matrix[srci][dsti] = w; //无向图 if (Direction == false) { _matrix[dsti][srci] = w; } } void Print() { // 顶点 for (size_t i = 0; i < _vertexs.size(); i++) { cout << "[" << i << "]" << "->" << _vertexs[i] << endl; } cout << endl; //矩阵 for (int i = 0; i < _matrix.size(); i++) { for (int j = 0; j < _matrix[i].size(); j++) { if (_matrix[i][j] == INT_MAX) { cout << "∞ "; } else { cout << _matrix[i][j] << " "; } } cout << endl; } cout << endl; } private: vector<V> _vertexs; //顶点集合 map<V, int> _indexMap; //顶点映射的下标 vector<vector<W>> _matrix; //邻接矩阵 }; void TestGraph() { Graph<char, int, INT_MAX, true> g("0123", 4); g.AddEdge('0', '1', 1); g.AddEdge('0', '3', 4); g.AddEdge('1', '3', 2); g.AddEdge('1', '2', 9); g.AddEdge('2', '3', 8); g.AddEdge('2', '1', 5); g.AddEdge('2', '0', 3); g.AddEdge('3', '2', 6); g.Print(); } }2.2 邻接表
邻接表：使用数组表示顶点的集合，使用链表表示边的关系。
1. 无向图邻接表存储
注意：无向图中同一条边在邻接表中出现了两次。如果想知道顶点vi的度，只需要知道顶点 vi边链表集合中结点的数目即可。
2. 有向图邻接表存储
一般情况下有向图，存储一个出边表即可。
注意：
有向图中每条边在邻接表中只出现一次，与顶点vi对应的邻接表所含结点的个数，就 是该顶点的出度，也称出度表，要得到vi顶点的入度，必须检测其他所有顶点对应的边链 表，看有多少边顶点的dst取值是i。
邻接表优点：
- 适合存储稀疏图。
- 适合查找一个顶点连接出去的边
邻接表缺点：
- 不适合确定两个顶点是否相连及权值
代码实现（如下）
//邻接表 namespace link_table { template<class W> struct Edge { int _dsti; //目标点的下标 W _w; //权值 Edge<W>* _next; Edge(int dsti, const W& w) :_dsti(dsti) , _w(w) ,_next(nullptr) {} }; //vertex：边 weight：权值 false表示无向图，true表示有向图 template<class V, class W, bool Direction = false> class Graph { typedef Edge<W> Edge; public: Graph(const V* a, size_t n) { _vertexs.reserve(n); for (size_t i = 0; i < n; i++) { _vertexs.push_back(a[i]); _indexMap[a[i]] = i; } _tables.resize(n, nullptr); } size_t GetVertexIndex(const V& v) { auto it = _indexMap.find(v); if (it != _indexMap.end()) { return it->second; } else { assert(false); return -1; } } void AddEdge(const V& src, const V& dst, const W& w) { size_t srci = GetVertexIndex(src); size_t dsti = GetVertexIndex(dst); //1->2 //头插 Edge* eg = new Edge(dsti,w); eg->_next = _tables[srci]; _tables[srci] = eg; //2->1 if (Direction == false) //无向表 { Edge* eg = new Edge(srci, w); eg->_next = _tables[dsti]; _tables[dsti] = eg; } } void Print() { // 顶点 for (size_t i = 0; i < _vertexs.size(); i++) { cout << "[" << i << "]" << "->" << _vertexs[i] << endl; } cout << endl; for (int i = 0; i < _tables.size(); i++) { cout << _vertexs[i] << "[" << i << "]->"; Edge* cur = _tables[i]; while (cur) { cout << _vertexs[cur->_dsti] << "[" << cur->_dsti << "]"<<cur->_w<<"->"; cur = cur->_next; } cout << "null" << endl; } } private: vector<V> _vertexs; //顶点集合 map<V, int> _indexMap; //顶点映射的下标 vector<Edge*> _tables; //邻接表 }; void TestGraph() { //Graph<char, int, INT_MAX, true> g("0123", 4); //g.AddEdge('0', '1', 1); //g.AddEdge('0', '3', 4); //g.AddEdge('1', '3', 2); //g.AddEdge('1', '2', 9); //g.AddEdge('2', '3', 8); //g.AddEdge('2', '1', 5); //g.AddEdge('2', '0', 3); //g.AddEdge('3', '2', 6); //g.Print(); string a[] = { "张三", "李四", "王五", "赵六" }; Graph<string, int,true> g1(a, 4); g1.AddEdge("张三", "李四", 100); g1.AddEdge("张三", "王五", 200); g1.AddEdge("王五", "赵六", 30); g1.Print(); } }总结
- 邻接矩阵和邻接表其实属于相辅相成，各有优缺点的互补结构
3. 图的遍历
给定一个图G和其中任意一个顶点v0，从v0出发，沿着图中各边访问图中的所有顶点，且每个顶点仅被遍历一次。"遍历"即对结点进行某种操作的意思。
3.1 图的广度优先遍历
代码实现（使用的邻接矩阵）：
void BFS(const V& src) { int srci = GetVertexIndex(src); //队列和标记数组 queue<int> q; vector<bool> visited(_vertexs.size(), false); q.push(srci); visited[srci] = true; int levelSize = 1; while (!q.empty()) { //一层一层出 for (int i = 0; i < levelSize; i++) { int front = q.front(); cout << front << ":" << _vertexs[front] << " "; q.pop(); //把front顶点的邻接顶点入队列 for (int i = 0; i < _matrix.size(); i++) { if (visited[i] == false && _matrix[front][i] != MAX_W) { q.push(i); visited[i] = true; } } } cout << endl; levelSize = q.size(); } }3.2 图的深度优先遍历
代码实现（如下）：
void _DFS(int srci, vector<bool>& visited) { cout << srci << ":" << _vertexs[srci] <<endl; visited[srci] = true; //找一个srci相邻的没有访问过点，去往深度遍历 for (int i = 0;i<_vertexs.size();i++) { if (_matrix[srci][i] != MAX_W && visited[i] == false) { _DFS(i, visited); } } } void DFS(const V& src) { int srci = GetVertexIndex(src); vector<bool> visited(_vertexs.size(),false); _DFS(srci,visited); }4.最小生成树
连通图中的每一棵生成树，都是原图的一个极大无环子图，即：从其中删去任何一条边，生成树就不在连通；反之，在其中引入任何一条新边，都会形成一条回路。
若连通图由n个顶点组成，则其生成树必含n个顶点和n-1条边。因此构造最小生成树的准则有三条
- 只能使用图中权值最小的边来构造最小生成树
- 只能使用恰好n-1条边来连接图中的n个顶点
- 选用的n-1条边不能构成回路
构造最小生成树的方法：Kruskal算法和Prim算法。这两个算法都采用了逐步求解的贪心策略。
最小生成树：构成生成树这些边加起来权值是最小的。（最小的成本使N个顶点连接起来）
贪心算法：是指在问题求解时，总是做出当前看起来最好的选择。也就是说贪心算法做出的不是 整体最优的的选择，而是某种意义上的局部最优解。贪心算法不是对所有的问题都能得到整体最优解。
4.1 Kruskal算法
任给一个有n个顶点的连通网络N={V,E}，首先构造一个由这n个顶点组成、不含任何边的图G={V,NULL}，其中每个顶点自成一个连通分量， 其次不断从E中取出权值最小的一条边(若有多条任取其一)，若该边的两个顶点来自不同的连通分量，则将此边加入到G中。如此重复，直到所有顶点在同一个连通分量上为止。
核心：每次迭代时，选出一条具有最小权值，且两端点不在同一连通分量上的边，加入生成树。
判环 —— 利用并查集
代码实现（如下）
typedef Graph<V, W, MAX_W, Direction> Self; //Kruskal算法 struct Edge { int _srci; int _dsti; W _w; Edge(int srci,int dsti,const W& w) :_srci(srci) ,_dsti(dsti) ,_w(w) {} bool operator>( const Edge& e) const { return _w > e._w; } }; W Kruskal(Self& minTree) { int n = _vertexs.size(); minTree._vertexs = _vertexs; minTree._indexMap = _indexMap; minTree._matrix.resize(n); for (int i = 0; i < n; i++) { minTree._matrix[i].resize(n,MAX_W); } //优先级队列 priority_queue<Edge , vector<Edge>,greater<Edge>> minque; //将全部边放入优先级队列，一定是无向图 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i<j && _matrix[i][j] != MAX_W) { minque.push(Edge(i, j, _matrix[i][j])); } } } //选出n-1条边 int size =0; W totalW = W(); UnionFindSet ufs(n); while (!minque.empty()) { Edge min = minque.top(); minque.pop(); if (!ufs.InSet(min._srci, min._dsti)) { minTree.AddEdge(min._srci, min._dsti, min._w); ufs.Union(min._srci, min._dsti); ++size; totalW += min._w; } else { cout << "构成环:"; } } if (size == n - 1) { return totalW; } else { return W(); } }4.2 Prim算法
与Kruskal算法类似，Prim算法也是通用的最小生成树的一个特例。Prim算法的工作原理与Dijkstra的最短路径算法相似。Prim算法所具有的一个性质是集合A中的边构成一棵树。这棵树从一个任意的跟节点r开始，一直长大到覆盖V中的所有结点时为止。（如下图所示）
代码实现（如下）
//Prim算法 W Prim(Self& minTree,const V& src) { int srci = GetVertexIndex(src); int n = _vertexs.size(); //初始化 minTree._vertexs = _vertexs; minTree._indexMap = _indexMap; minTree._matrix.resize(n); for (int i = 0; i < n; i++) { minTree._matrix[i].resize(n, MAX_W); } //创建两个集合 vector<bool> X(n,false); vector<bool> Y(n,true); X[srci] = true; Y[srci] = false; //从X->Y集合中连接的边里面选出最小的边 priority_queue<Edge, vector<Edge>, greater<Edge>> minq; //先把srci连接的边添加到队列中 for (int i = 0; i < n; i++) { if (_matrix[srci][i] != MAX_W) { minq.push(Edge(srci,i, _matrix[srci][i])); } } int i = 0; W totalw = W(); while (!minq.empty()) { Edge min = minq.top(); minq.pop(); //最小边的目标点也在X集合，则构成环 if (X[min._dsti]) { //cout << "形成了环" << endl; } else { minTree.AddEdge(min._srci, min._dsti, min._w); X[min._dsti] = true; Y[min._dsti] = false; i++; totalw += min._w; if (i == n - 1) break; for (int i = 0; i < n; i++) { if (_matrix[min._dsti][i] != MAX_W && Y[i]) { minq.push(Edge(min._dsti, i, _matrix[min._dsti][i])); } } } } if (i == n - 1) { return totalw; } else { return W(); } }5.最短路径
最短路径问题：从在带权有向图G中的某一顶点出发，找出一条通往另一顶点的最短路径，最短也就是 沿路径各边的权值总和达到最小。
5.1 单源最短路径--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算法存在的问题是不支持图中带负权路径，如果带有负权路径，则可能会找不到一些路 径的最短路径。
代码实现：
//最短路径——Dijkstra算法 void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath) { int srci = GetVertexIndex(src); int n = _vertexs.size(); dist.resize(n, MAX_W); pPath.resize(n, -1); dist[srci] = 0; pPath[srci] = srci; //已经确定最短路径的顶点集合 vector<bool> S(n,false); for (int j = 0; j < n; j++) { //选最短路径的顶点且不在S更新其他路径 int u = 0; W min = MAX_W; for (int i = 0; i < n; i++) { if (S[i] == false && dist[i] < min) { u = i; min = dist[i]; } } S[u] = true; //松弛更新u连接顶点v srci->u u->v 《 srci->v 更新 for (int v = 0; v < n; v++) { if (_matrix[u][v] != MAX_W && dist[u] + _matrix[u][v] < dist[v]) { dist[v] = dist[u] + _matrix[u][v]; pPath[v] = u; } } } } //打印最短路径 void PrinrtShotPath(const V& src, const vector<W>& dist, const vector<int>& parentPath) { size_t N = _vertexs.size(); size_t srci = GetVertexIndex(src); for (size_t i = 0; i < N; ++i) { if (i == srci) continue; vector<int> path; int parenti = i; while (parenti != srci) { path.push_back(parenti); parenti = parentPath[parenti]; } path.push_back(srci); reverse(path.begin(), path.end()); for (auto pos : path) { cout << _vertexs[pos] << "->"; } cout << dist[i] << endl; } }
