图、最小生成树与最短路径

并查集

并查集实现

图

概念

图的存储结构

邻接矩阵

邻接表

无向图

有向图

图的遍历

广度优先遍历

深度优先遍历

最小生成树

Kruskal算法（克鲁斯卡尔算法）

Prim算法（普利姆算法）

最短路径

单源最短路径--Dijkstra算法（迪杰斯特拉算法）

单源最短路径--Bellman-Ford算法（贝尔曼-福特算法）

多源最短路径--Floyd-Warshall算法

并查集

并查集，就是用来解决这种问题的数据结构

以上面这张图为例，一开始的时候，每一个元素之间都是单独的集合。我们此时可能会查看两个元素之间的集合关系，也就是是否归属于同一个集合，也有可能会将两个元素进行合并，合并到同一个集合当中去

例如上面，6,7,8都属于0所在的集合

4,9都属于1所在的集合

3,5都属于2所在的集合

我们将1所在的集合与0所在的集合进行合并操作，这样他们都属于同一个集合：0

当然，也可以选择将0号集合全部都放入1号集合中。从结果上来说是一样的，都属于同一个集合

根据上面的图，我们可以发现，每一个属于同一个集合的元素，要不是他们自己，要不是他们所在的集合，都属于同一个集合当中，而他们所在的集合都以下标为单位

每一个元素在一开始时候的值为-1，这样，他们的取值如果为负数，则说明他们本身就是一个集合的最上层，那么这个值取正，就是一个集合的元素个数

如果他们的值为正，那么，他们的值实际上就是他的“上一层”元素的下标，有可能这个下标所对应元素的值为负，也就是集合最上层的元素所在位置。也有可能只是这一整个集合的某一个普通元素

因此，我们可以将并查集的功能划分如下：
1.查找当前元素所在的集合（也就是最上层元素的下标）

2.合并两个元素（也就是对两个元素所在的集合进行合并，如果他们是同一个集合就不用合并，不同才需要合并）

3.集合的个数（所有值为负数的元素个数）

并查集实现

class UnionFindSet
{
public:UnionFindSet(int n) :vec(n, -1) {}int FindRoot(int x)//查找一个元素所在的集合{int root = x;while (vec[root] >= 0)root = vec[root];return root;}void UnionSet(int x1, int x2)//合并两个元素所在的大集合{int root1 = FindRoot(x1);int root2 = FindRoot(x2);if (root1 == root2)return;vec[root1] += vec[root2];vec[root2] = root1;}int SetSize(){int sum = 0;for (int i = 0;i < vec.size();++i){if (vec[i] < 0){++sum;}}return sum;}
private:vector<int> vec;
};

其中我们也可以做一些优化，主要是两个：

1.合并时，将元素个数少的集合，合并到元素个数多的集合当中（如果是元素个数多的放入元素个数少的中，那么就会有更多的元素在查找最顶层时比起之前多访问一次）

void UnionSet(int x1, int x2)//合并两个元素所在的大集合{int root1 = FindRoot(x1);int root2 = FindRoot(x2);if (root1 == root2)return;if (abs(vec[root1])<abs(vec[root2]))//将小集合塞入大集合std::swap(root1,root2);vec[root1] += vec[root2];vec[root2] = root1;}

2.查找集合顶层元素下标时，将当前元素对应的一整条分支，都直接划分到顶层的下方，这样可以减少查找顶层时的访问次数（路径压缩）

int FindRoot(int x)//查找一个元素所在的集合{int root = x;while (vec[root] >= 0)root = vec[root];while (vec[x] >= 0)//路径压缩{int parent = vec[x];vec[x] = root;x = parent;}return root;}

图

我们前面讲并查集，除了合并问题外，主要就是为了图服务

概念

图是由顶点集合及顶点间的关系组成的一种数据结构：G = (V， E)

顶点集合V = {x|x属于某个数据对象集}是有穷非空集合

E = {(x,y)|x,y属于V}或者E = {<x, y>|x,y属于V && Path(x, y)}是顶点间关系的有穷集合，也叫
做边的集合

(x, y)表示x到y的一条双向通路，即(x, y)是无方向的；Path(x, y)表示从x到y的一条单向通路，即
Path(x, y)是有方向的

顶点和边：图中结点称为顶点，第i个顶点记作vi。两个顶点vi和vj相关联称作顶点vi和顶点vj之间
有一条边，图中的第k条边记作ek，ek = (vi，vj)或<vi，vj>

有向图和无向图

直接看图，上图中的G1与G2，他们的边没有方向，是双向关系，因此是无向图

而G3与G4，他们的边明确有着方向，因此是有向图

完全图：

任意两个顶点之间，都有边可以直接到达

在无向图中，由于边是没有方向的，因此只需要任意两个顶点都存在一条边即可

边数为:n*(n-1)/2

而在有向图中，边存在方向，因此需要任意两个顶点中存在两条边

边数为: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相关联

顶点的度

顶点的度，就是一个与某一个顶点相关联的边的个数，记作deg(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的子图

子图也就是原来图的一部分，就叫做子图(比原来的图少掉几条边，或者顶点)

连通图

在无向图中，如果任意一个顶点，都可以通过某条路径到达任意一个其他顶点，那么这样的图叫做连通图，顶多数最少为n-1

强连通图

与连通图的区别是，连通图是无向图的概念，而强连通图则是有向图中的概念，要求与连通图是一样的，顶点数最少为2*(n-1)

图的存储结构

图的话只需要保存两个东西，顶点与边

顶点只需要一段连续空间即可，而顶点则有以下两种存储方式

邻接矩阵

采用矩阵的方式，保存两个顶点之间的关系（0与1代表是否联通）。如果边是带权的，那么就采用默认值（无穷大）与权值来表示两个顶点之间的关系

注意：

无向图的邻接矩阵是对称的，第i行(列)元素之和，就是顶点i的度。有向图的邻接矩阵则不一
定是对称的，第i行(列)元素之后就是顶点i的出(入)度

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

template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph
{
public:typedef Graph<V, W, MAX_W, Direction> Self;//定义当前类Graph() = default;Graph(const V* vertexs, size_t n)；//初始化顶点size_t GetVertexIndex(const V& v)；//获取顶点对应的下标void _AddEdge(size_t srci, size_t dsti, const W& w)；//根据顶点下标来添加边void AddEdge(const V& src, const V& dst, const W& w)；//根据顶点来添加边map<V, size_t> _vIndexMap;//存储顶点与所在位置的对应关系vector<V> _vertexs; // 顶点集合，采用数组存储vector<vector<W>> _matrix; // 存储边集合的矩阵
};

邻接表

邻接矩阵最大的好处，就是查找两个顶点之间的连接关系，但是更适合稠密图（边比较多，顶点之间连接关系比较复杂）

但是如果对于边比较少，顶点个数又很多的情况，邻接矩阵就非常的浪费空间了

因此，我们可以将矩阵改为链表，通过链表来存储顶点之间的连接关系

无向图

在无向图中，邻接表存储的是两个顶点的连接关系，也就是说两个顶点相连的话，那么就需要在两个链表中各自添加一份链表节点

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

有向图

注意：有向图中每条边在邻接表中只出现一次，与顶点vi对应的邻接表所含结点的个数，就
是该顶点的出度，也称出度表，要得到vi顶点的入度，必须检测其他所有顶点对应的边链表，看有多少边顶点的dst取值是i（也就是只有一张表存储的话，只有入读或出度的其中一个可以快速查找，另一个就很慢了，要遍历所有节点的连接关系）。

template<class W>
struct LinkEdge//边的关系，存储源节点，目标节点，权值，以及链表存储
{int _srcIndex;int _dstIndex;W _w;LinkEdge<W>* _next;LinkEdge(const W& w): _srcIndex(-1), _dstIndex(-1), _w(w), _next(nullptr){}
};template<class V, class W, bool Direction = false>
class Graph
{typedef LinkEdge<W> Edge;//定义边Graph(const V* vertexs, size_t n)；//初始化顶点集合size_t GetVertexIndex(const V& v)；//获取顶点对应的下标void AddEdge(const V& src, const V& dst, const W& w)；//增加边private:map<V, int> _vIndexMap;//vector<V> _vertexs; // 顶点集合vector<Edge*> _linkTable; // 边的集合的邻接表
};

图的遍历

这个的话，在算法题里应该都学过，两种

举个例子：

现在有一批套娃的盒子，每个盒子里面可能是小盒子，我们怎样去查看每个盒子里面是怎么装的

广度优先遍历

我们选择先把每一个盒子都给拆开，如果盒子里还有盒子就先放着，等下一轮再拆

这种访问后可以继续访问但是先留着去访问其他就是广度优先遍历

二叉树的层序遍历也是这种思想

void BFS(const V& src)
{size_t srcindex = GetVertexIndex(src);vector<bool> visited;visited.resize(_vertexs.size(), false);queue<int> q;q.push(srcindex);visited[srcindex] = true;size_t d = 1;size_t dSize = 1;while (!q.empty()){printf("%s的%d度好友:", src.c_str(), d);while (dSize--){size_t front = q.front();q.pop();for (size_t i = 0; i < _vertexs.size(); ++i){if (visited[i] == false && _matrix[front][i] != MAX_W){printf("[%d:%s] ", i, _vertexs[i].c_str());visited[i] = true;q.push(i);}}}cout << endl;dSize = q.size();++d;}cout << endl;
}

深度优先遍历

我们拆开某一个盒子后，如果盒子里还有盒子，就继续拆，直到这个盒子被拆完为止

这种如果可以访问就继续访问直到没法访问就是深度优先遍历

void _DFS(int index, vector<bool>& visited)//单次执行的操作
{if(!visited[index]){cout<<_v[index]<<" ";visited[index] = true;LinkEdge* pCur = _linkEdges[index];while(pCur){_DFS(pCur->_dst, visited);pCur = pCur->_pNext;}}
}
void DFS(const V& v)//深度优先
{cout<<"DFS:";vector<bool> visited(_v.size(), false);_DFS(GetIndexOfV(v), visited);for(size_t index = 0; index < _v.size(); ++index)_DFS(index, visited);cout<<endl;
}

最小生成树

连通图中的每一棵生成树，都是原图的一个极大无环子图，即：从其中删去任何一条边，生成树
就不在连通；反之，在其中引入任何一条新边，都会形成一条回路（我们前面讲的并查集，就是用来判断，两个节点相连之后，是否会成环）

最小生成树则是在所有生成树中，权值总和最小

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

1.只能使用图中的边来构造最小生成树

2.只能使用恰好n-1条边来连接图中的n个顶点

3.选用的n-1条边不能构成回路

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

贪心算法：是指在问题求解时，总是做出当前看起来最好的选择。也就是说贪心算法做出的不是
整体最优的的选择，而是某种意义上的局部最优解

贪心算法不是对所有的问题都能得到整体最优解

Kruskal算法（克鲁斯卡尔算法）

步骤

将所有的边的权值进行排序（放入堆中），每一次都取权值最小且不会成环的的边（这里就用到了并查集，只要插入边的起点与终点所在的集合不是同一个，那么就不会成环）

每次增加一条边，边的总数为n-1即可

我们最后是否形成了最小生成树的判断条件就是看我们取到的边的个数是否是n-1条边即可

至于这个算法的正确性，我们只需要知道有一个定理

切分定理（研究克鲁斯卡尔算法正确性过程中得出的结论）

简单来说就是：

我们将图中的节点分为两部分，这种操作叫切分

存在一条边可以连接这两部分，并且它的权值是最短的，那么这条边就属于最小生成树

证明

我们假设，切分后的两部分，都是联通的。那么我们现在需要连接这两部分，就可以让整张图是联通的。那么我们既然是要形成最小生成树，那么我们要寻找的边，就绝对是可以连接两部分的权值最小的边。

这样，我们就证明了切分后存在一条连接两部分的权值最短的边属于最小生成树

W Kruskal(Self& minTree)
{minTree._vertexs = _vertexs;minTree._vIndexMap = _vIndexMap;minTree._matrix.resize(_vertexs.size());for (auto& e : minTree._matrix){e.resize(_vertexs.size(), MAX_W);}priority_queue<Edge, vector<Edge>, greater<Edge>> pq;for (size_t i = 0; i < _matrix.size(); ++i){for (size_t j = 0; j < _matrix[i].size(); ++j){if (i < j && _matrix[i][j] != MAX_W){pq.push(Edge(i, j, _matrix[i][j]));}}}W total = W();size_t i = 1;UnionFindSet ufs(_vertexs.size());while (i < _vertexs.size() && !pq.empty()){Edge min = pq.top();pq.pop();// 边不在一个集合，说明不会构成环，则添加到最小生成树if (ufs.FindRoot(min._srci) != ufs.FindRoot(min._dsti)){minTree._AddEdge(min._srci, min._dsti, min._w);total += min._w;ufs.Union(min._srci, min._dsti);++i;}}if (i == _vertexs.size()){return total;}else{return W();}
}

Prim算法（普利姆算法）

Kruskal算法的操作，是将所有的边都取出来，按照边的最小值的顺序来获取最小生成树

而Prim算法的操作，则是以点为顺序，每次都固定在集合中放入一个节点

每次增加一个点，点的总数为n即可

步骤

每次取一个点，同时将该点所能连接的边放入堆中

然后我们对堆排序好的边进行选择。

我们要求选择到的边，首先他的终点不能在已经访问过的节点集合中（不能成环），在这个条件下，权值最小的边，就是我们要选择的边。

将该边的终点放入队列，同时将该点所有终点不在集合中的边放入堆中即可

最后的退出条件为堆空或者取到的点已经达到了n个

W Prim(Self& minTree, const V& src)
{minTree._vertexs = _vertexs;minTree._vIndexMap = _vIndexMap;minTree._matrix.resize(_vertexs.size());for (auto& e : minTree._matrix){e.resize(_vertexs.size(), MAX_W);}size_t srci = GetVertexIndex(src);set<size_t> inSet;inSet.insert(srci);priority_queue<Edge, vector<Edge>, greater<Edge>> pq;for (size_t i = 0; i < _vertexs.size(); ++i){if (_matrix[srci][i] != MAX_W){pq.push(Edge(srci, i, _matrix[srci][i]));}}W total = W();while (inSet.size() < _vertexs.size() && !pq.empty()){Edge min = pq.top();pq.pop();// 防止环的问题if (inSet.find(min._srci) == inSet.end() ||inSet.find(min._dsti) == inSet.end()){minTree._AddEdge(min._srci, min._dsti, min._w);total += min._w;// 新入顶点的连接边进入队列for (size_t i = 0; i < _vertexs.size(); ++i){if (_matrix[min._dsti][i] != MAX_W && inSet.find(i) == inSet.end()){pq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));}}inSet.insert(min._dsti);}}if (inSet.size() == _vertexs.size()){return total;}else{return W();}
}

最短路径

最短路径问题：从在带权有向图G中的某一顶点出发，找出一条通往另一顶点的最短路径，最短也就是沿路径各边的权值总和达到最小

单源最短路径--Dijkstra算法（迪杰斯特拉算法）

Dijkstra算法就适用于解决带权重的有向图上的单源最短路径问题，同时算法要求图中所有边的权重非负

一般在求解最短路径的时候都是已知一个起点和一个终点，所以使用Dijkstra算法求解过后也就得到了所需起点到终点的最短路径

Dijkstra算法存在的问题是不支持图中带负权路径，如果带有负权路径，则可能会找不到一些路
径的最短路径

该算法最核心的是：每一次遍历都可以找出某一个节点到起始节点的最短路径

步骤

1.找到没有访问过的最短路径节点（已经找到了最短路径的节点）中，路径最短的节点

2.尝试更新这个节点所能经过的所有节点的最短路径（已经确认过最短路径的话就没必要再访问了，是否需要更新需要判断当前节点的路径与两个节点的权值之和是否小于该节点此时保存的最短路径）

3.经过更新后，又可以多出来一个确认最短路径的节点，重复上述操作n次，刚好确认所有最短路径

这个算法最核心的地方在于每一次都可以确认一个节点的最短路径，原因是什么？

1.循环过程中，我们能找到的最短路径节点，是没有之前没有访问过的最短路径节点。轮到它的原因，则是所有比他路径短的节点都修改过它了，已经没有未访问的节点比他更短了（也就不可能更短）。

2.这意味着，前面所有比他路径更短的节点，已经完成了他们的更新工作

3.轮到他的时候，它能够访问的节点，要不就是比他短路径短的节点访问不到，要不就是访问并且更新过（访问到它时也就无法被再次修改了）。

4.所以它更改的节点，绝对会比之前的路径更短。也就确认了此时，绝对会有一个新的最短路径节点产生（两种可能，要不就是在它此时更改的节点当中，要不就是其他未访问的最短路径节点被确定）

以上原因，则是为什么Dijkstra算法每一次都可以更新出（确认）一个新的最短路径节点

void Dijkstra(const V& src, vector<W>& dist, vector<int>& parentPath)
{size_t N = _vertexs.size();size_t srci = GetVertexIndex(src);// vector<W> dist,记录srci-其他顶点最短路径权值数组dist.resize(N, MAX_W);// vector<int> parentPath 记录srci-其他顶点最短路径父顶点数组parentPath.resize(N, -1);// 标记是否找到最短路径的顶点集合Svector<bool> S;S.resize(N, false);// srci的权值给一个最小值，方便贪心第一次找到这个节点dist[srci] = W();// N个顶点更新N次for (size_t i = 0; i < N; ++i){// 贪心算法：srci到不在S中路径最短的那个顶点uW min = MAX_W;size_t u = srci;for (size_t j = 0; j < N; ++j){if (S[j] == false && dist[j] < min){min = dist[j];u = j;}}S[u] = true;// 松弛算法：更新一遍u连接的所有边，看是否能更新出更短连接路径for (size_t k = 0; k < N; ++k){// 如果srci->u + u->k 比 srci->k更短 则进行更新if (S[k] == false && _matrix[u][k] != MAX_W&& dist[u] + _matrix[u][k] <dist[k]){dist[k] = dist[u] + _matrix[u][k];parentPath[k] = u;}}}
}

单源最短路径--Bellman-Ford算法（贝尔曼-福特算法）

Dijkstra算法算法解决的时无负权的最短路径问题

Bellman-Ford解决的是有负权的最短路径问题

不过，如果有负环（环的权重之和为负）的存在，那么就不会有最短路径，因为同一个顶点每经过一轮负环，权重就会减少，不会存在最短路径

步骤

1.设置源节点路径为0，其他节点值为∞

2.对每个节点都按照边的权值进行路径更新

3.以上更新操作执行n-1次

4.如果更新完之后，还可以继续更新，说明存在负环，不存在最短路径

我们为什么可以保证经历n-1轮更新操作之后，此时所有路径都达到最短路径，如果可以继续更新那么就存在负环？

1.节点总数为n，n-1次更新已经可以涵盖所有路径情况了

2.如果n-1轮过后还可以继续更新，说明某一个节点，它的最短路径为负数（因为负环的存在），这种情况显然是不可能的，因此我们可以判断存在负环

bool BellmanFord(const V& src, vector<W>& dist, vector<int>& parentPath)
{size_t N = _vertexs.size();size_t srci = GetVertexIndex(src);// vector<W> dist,记录srci-其他顶点最短路径权值数组dist.resize(N, MAX_W);// vector<int> parentPath 记录srci-其他顶点最短路径父顶点数组parentPath.resize(N, -1);// 先更新srci->srci为最小值dist[srci] = W();for (size_t k = 0; k < N - 1; ++k){bool exchange = false;for (size_t i = 0; i < N; ++i){for (size_t j = 0; j < N; ++j){// srci->i + i->j < srci->j 则更新路径及权值if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j]){dist[j] = dist[i] + _matrix[i][j];parentPath[j] = i;exchange = true;}}}if (exchange == false)//没有更新过，那么就直接退出break;}for (size_t i = 0; i < N; ++i){for (size_t j = 0; j < N; ++j){// 检查有没有负权回路if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j]){return false;}}}return true;
}

当然，我们也可以对这个算法做一点点小优化，将所有被修改的节点放入队列，将该节点所有可以访问到的节点进行判断能否修改，如果可以修改就将修改后的节点再次放入队列，直到队列为空

不过这种优化后的算法有了个新名字：SPFA算法。时间复杂度上比Bellman-Ford算法号不少。

SPFA算法的时间复杂度为O(n^2)，而Bellman-Ford则高达O(n^3)

多源最短路径--Floyd-Warshall算法

Floyd-Warshall算法是解决任意两点间的最短路径的一种算法

这种算法的原理是动态规划

步骤

以某个节点作为中介，修改以该节点为中介的两侧节点即可

void FloydWarShall(vector<vector<W>>& vvDist, vector<vector<int>>& vvParentPath)
{size_t N = _vertexs.size();vvDist.resize(N);vvParentPath.resize(N);// 初始化权值和路径矩阵for (size_t i = 0; i < N; ++i){vvDist[i].resize(N, MAX_W);vvParentPath[i].resize(N, -1);}// 将直接相连的路径初始化for (size_t i = 0; i < N; ++i){for (size_t j = 0; j < N; ++j){if (_matrix[i][j] != MAX_W){vvDist[i][j] = _matrix[i][j];vvParentPath[i][j] = i;}else{vvParentPath[i][j] = -1;}if (i == j){vvDist[i][j] = 0;vvParentPath[i][j] = -1;}}}// 依次用顶点k作为中转点更新最短路径for (size_t k = 0; k < N; ++k){for (size_t i = 0; i < N; ++i){for (size_t j = 0; j < N; ++j){// i->k + k->j 比 i->j前面更新的距离更短，则更新if (vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W&& vvDist[i][k] + vvDist[k][j] < vvDist[i][j]){vvDist[i][j] = vvDist[i][k] + vvDist[k][j];vvParentPath[i][j] = vvParentPath[k][j];}}}}
}