DS图(中)(19)
文章目录
- 前言
- 一、图的遍历
- 广度优先遍历
- 深度优先遍历
- 二、最小生成树
- Kruskal算法
- Prim算法
- 两种方法对比
- 总结
前言
承上启下，我们来学习下图的中篇！！！
一、图的遍历
图的遍历指的是遍历图中的顶点，主要有 广度优先遍历 和 深度优先遍历 两种方式。
广度优先遍历
广度优先遍历又称BFS，其遍历过程类似于二叉树的层序遍历，从起始顶点开始一层一层向外进行遍历。
广度优先遍历的实现：
- 广度优先遍历需要借助一个队列和一个标记数组，利用队列先进先出的特点实现一层一层向外遍历，利用标记数组来记录各个顶点是否被访问过。
- 刚开始时将起始顶点入队列，并将起始顶点标记为访问过，然后不断从队列中取出顶点进行访问，并判断该顶点是否有邻接顶点，如果有邻接顶点并且该邻接顶点没有被访问过，则将该邻接顶点入队列，并在入队列后立即将该邻接顶点标记为访问过。
void BFS(const V& src)
{
size_t srci = GetVertexIndex(src);
// 队列和标记数组
queue<int> q;
vector<bool> visited(_vertexs.size(), false);
q.push(srci);
visited[srci] = true;
int levelSize = 1;
size_t n = _vertexs.size();
while (!q.empty())
{
// 一层一层出
for (int i = 0; i < levelSize; ++i)
{
int front = q.front();
q.pop();
cout << front << ":" << _vertexs[front] << " ";
// 把front顶点的邻接顶点入队列
for (size_t i = 0; i < n; ++i)
{
if (_matrix[front][i] != MAX_W)
{
if (visited[i] == false)
{
q.push(i);
visited[i] = true;
}
}
}
}
cout << endl;
levelSize = q.size();
}
cout << endl;
}
-
为了防止顶点被重复加入队列导致死循环，因此需要一个标记数组，当一个顶点被访问过后就不应该再将其加入队列了。
-
如果当一个顶点从队列中取出访问时才再将其标记为访问过，也可能会存在顶点被重复加入队列的情况，比如当图中的顶点B出队列时，顶点C作为顶点B的邻接顶点并且还没有被访问过（顶点C还在队列中），此时顶点C就会再次被加入队列，因此最好在一个顶点被入队列时就将其标记为访问过。
-
如果所给图不是一个连通图，那么从一个顶点开始进行广度优先遍历，无法遍历完图中的所有顶点，这时可以遍历标记数组，查看哪些顶点还没有被访问过，对于没有被访问过的顶点，则从该顶点处继续进行广度优先遍历，直到图中所有的顶点都被访问过。
深度优先遍历
深度优先遍历又称DFS，其遍历过程类似于二叉树的先序遍历，从起始顶点开始不断对顶点进行深入遍历。
深度优先遍历的实现：
- 深度优先遍历可以通过递归实现，同时也需要借助一个标记数组来记录各个顶点是否被访问过。
- 从起始顶点处开始进行递归遍历，在遍历过程中先对当前顶点进行访问，并将其标记为访问过，然后判断该顶点是否有邻接顶点，如果有邻接顶点并且该邻接顶点没有被访问过，则递归遍历该邻接顶点。
void _DFS(size_t srci, vector<bool>& visited)
{
cout << srci << ":" << _vertexs[srci] << endl;
visited[srci] = true;
// 找一个srci相邻的没有访问过的点，去往深度遍历
for (size_t i = 0; i < _vertexs.size(); ++i)
{
if (_matrix[srci][i] != MAX_W && visited[i] == false)
{
_DFS(i, visited);
}
}
}
void DFS(const V& src)
{
size_t srci = GetVertexIndex(src);
vector<bool> visited(_vertexs.size(), false);
_DFS(srci, visited);
}
- 如果所给图不是一个连通图，那么从一个顶点开始进行深度优先遍历，无法遍历完图中的所有顶点，这时可以遍历标记数组，查看哪些顶点还没有被访问过，对于没有被访问过的顶点，则从该顶点处继续进行深度优先遍历，直到图中所有的顶点都被访问过。
二、最小生成树
关于最小生成树
-
一个连通图的最小连通子图称为该图的生成树，若连通图由 n 个顶点组成，则其生成树必含 n 个顶点和 n−1 条边，最小生成树指的是一个图的生成树中，总权值最小的生成树。
-
连通图中的每一棵生成树都是原图的一个极大无环子图，从其中删去任何一条边，生成树就不再连通，在其中引入任何一条新边，都会形成一条回路。
-
对于各个顶点来说，除了第一个顶点之外，其他每个顶点想要连接到图中，至少需要一条边使其连接进来，所以由 n 个顶点的连通图的生成树有 n 个顶点和 n−1 条边。
-
对于生成树来说，图中的每个顶点已经连通了，如果再引入一条新边，那么必然会使得被新边相连的两个顶点之间存在一条直接路径和一条间接路径，即形成回路。
-
最小生成树是图的生成树中总权值最小的生成树，生成树是图的最小连通子图，而连通图是无向图的概念，有向图对应的是强连通图，所以最小生成树算法的处理对象都是无向图。
综上，我们可以得出以下生成 最小生成树 的准则
- 只能使用图中的边来构造最小生成树。
- 只能使用恰好 n−1 条边来连接图中的 n 个顶点。
- 选用的 n−1 条边不能构成回路。
构造最小生成树的算法有 Kruskal算法 和 Prim算法 ，这两个算法都采用了逐步求解的贪心策略。
Kruskal算法
Kruskal算法的基本思想如下：
- 构造一个含 n 个顶点、不含任何边的图作为最小生成树，对原图中的各个边按权值进行排序。
- 每次从原图中选出一条最小权值的边，将其加入到最小生成树中，如果加入这条边会使得最小生成树中构成回路，则重新选择一条边。
- 按照上述规则不断选边，当选出 n−1 条合法的边时，则说明最小生成树构造完毕，如果无法选出 n−1 条合法的边，则说明原图不存在最小生成树。
还记得我们之前学过的并查集么，如果忘记的话，快去复习一下吧！
-
根据原图设置最小生成树的顶点集合，以及顶点与下标的映射关系，开辟最小生成树的邻接矩阵空间，并将矩阵中的值初始化为 MAX_W ，表示刚开始时最小生成树中不含任何边。
-
遍历原图的邻接矩阵，按权值将原图中的所有边添加到优先级队列（小堆）中，为了避免重复添加相同的边，在遍历原图的邻接矩阵时只应该遍历矩阵的一半。
-
使用一个并查集来辅助判环操作，刚开始时图中的顶点各自为一个集合，当两个顶点相连时将这两个顶点对应的集合进行合并，使得连通的顶点在同一个集合，这样通过并查集就能判断所选的边是否会使得最小生成树中构成回路，如果所选边连接的两个顶点本就在同一个集合，那么加入这条边就会构成回路。
-
使用 count 和 totalWeight 分别记录所选边的数量和最小生成树的总权值，当 count 的值等于 n−1 时则停止选边，此时可以将最小生成树的总权值作为返回值进行返回。
-
每次选边时从优先级队列中获取一个权值最小的边，并通过并查集判断这条边连接的两个顶点是否在同一个集合，如果在则重新选边，如果不在则将这条边添加到最小生成树中，并将这条边连接的两个顶点对应的集合进行合并，同时更新 count 和 totalWeight 的值。
-
当选边结束时，如果 count 的值等于 n−1 ，则说明最小生成树构造成功，否则说明原图无法构造出最小生成树。
typedef Graph<V, W, MAX_W, Direction> Self;
struct Edge
{
size_t _srci;
size_t _dsti;
W _w;
Edge(size_t srci, size_t dsti, const W& w)
:_srci(srci)
,_dsti(dsti)
,_w(w)
{}
bool operator>(const Edge& e) const
{
return _w > e._w;
}
};
W Kruskal(Self& minTree)
{
size_t n = _vertexs.size();
minTree._vertexs = _vertexs;
minTree._indexMap = _indexMap;
minTree._matrix.resize(n);
for (size_t i = 0; i < n; ++i)
{
minTree._matrix[i].resize(n, MAX_W);
}
priority_queue<Edge, vector<Edge>, greater<Edge>> minque;
for (size_t i = 0; i < n; ++i)
{
for (size_t 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))
{
//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] <<":"<<min._w << endl;
minTree._AddEdge(min._srci, min._dsti, min._w);
ufs.Union(min._srci, min._dsti);
++size;
totalW += min._w;
}
else
{
//cout << "构成环：";
//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
}
}
if (size == n - 1)
{
return totalW;
}
else
{
return W();
}
}
-
在获取图的最小生成树时，会以无参的方式定义一个最小生成树对象，然后用原图对象调用上述 Kruskal函数 ，通过输出型参数的方式获取原图的最小生成树，由于我们定义了一个带参的构造函数，使得编译器不再生成默认构造函数，因此需要通过 default 关键字强制生成 Graph类 的默认构造函数。
-
一条边包含两个顶点和边的权值，可以定义一个Edge结构体来描述一条边，结构体内包含边的源顶点和目标顶点的下标以及边的权值，在使用优先级队列构造小堆结构时，需要存储的对象之间能够支持 > 运算符操作，因此需要对Edge结构体的 > 运算符进行重载，将其重载为边的权值的比较。
-
当选出的边不会构成回路时，需要将这条边插入到最小生成树对应的图中，此时已经知道了这条边的源顶点和目标顶点对应的下标，可以在 Graph类 中新增一个 _AddEdge 子函数，该函数支持通过源顶点和目标顶点的下标向图中插入边，而 Graph类 中原有的 AddEdge函数 可以复用这个 _AddEdge 子函数。
-
最小生成树不一定是唯一的，特别是当原图中存在很多权值相等的边的时候。
-
上述代码中通过优先级队列构造小堆来依次获取权值最小的边，你也可以通过其他排序算法按权值对边进行排序，然后按权值从小到大依次遍历各个边进行选边操作。
Prim算法
Prim算法的基本思想如下：
-
构造一个含 n 个顶点、不含任何边的图作为最小生成树，将图中的顶点分为两个集合，forest 集合中的顶点是已经连接到最小生成树中的顶点，remain 集合中的顶点是还没有连接到最小生成树中的顶点，刚开始时 forest 集合中只包含给定的起始顶点。
-
每次从连接 forest 集合与 remain 集合的所有边中选出一条权值最小的边，将其加入到最小生成树中，由于选出来的边对应的两个顶点一个属于 forest 集合，另一个属于 remain 集合，因此这种方法是天然不会构成回路的。
-
按照上述规则不断选边，当选出 n−1 条边时，所有的顶点都已经加入到了 forest 集合，此时最小生成树构造完毕，如果无法选出 n−1 条边，则说明原图不存在最小生成树。
-
根据原图设置最小生成树的顶点集合，以及顶点与下标的映射关系，开辟最小生成树的邻接矩阵空间，并将矩阵中的值初始化为 MAX_W ，表示刚开始时最小生成树中不含任何边。
-
使用一个 forest 数组来表示各个顶点是否在 forest 集合中，刚开始时只有起始顶点在 forest 集合中，并将所有从起始顶点连接出去的边加入优先级队列（小堆），这些边就是刚开始时连接 forest 集合与 remain 集合的边。
-
使用 count 和 totalWeight 分别记录所选边的数量和最小生成树的总权值，当 count 的值等于 n−1 时则停止选边，此时将最小生成树的总权值作为返回值进行返回。
-
每次选边时从优先级队列中获取一个权值最小的边，将这条边添加到最小生成树中，并将这条边的目标顶点加入 forest 集合中，同时更新 count 和 totalWeight 的值。
-
此外，还需要将从这条边的目标顶点连接出去的边加入优先级队列，但是需要保证加入的边的目标顶点不能在 forest 集合，否则后续选出源顶点和目标顶点都在 forest 集合的边就会构成回路。
-
需要注意的是，每次从优先级队列中选出一个权值最小的边时，还需要保证选出的这条边的目标顶点不在 forest 集合中，避免构成回路。虽然向优先级队列中加入边时保证了加入的边的目标顶点不在 forest 集合中，但经过后续不断的选边，可能会导致之前加入优先级队列中的某些边的目标顶点也被加入到了 forest 集合中。
-
当选边结束时，如果 count 的值等于 n−1 ，则说明最小生成树构造成功，否则说明原图无法构造出最小生成树。
W Prim(Self& minTree, const V& src)
{
size_t srci = GetVertexIndex(src);
size_t n = _vertexs.size();
minTree._vertexs = _vertexs;
minTree._indexMap = _indexMap;
minTree._matrix.resize(n);
for (size_t i = 0; i < n; ++i)
{
minTree._matrix[i].resize(n, MAX_W);
}
/*set<int> X;
set<int> Y;
X.insert(srci);
for (size_t i = 0; i < n; ++i)
{
if (i != srci)
{
Y.insert(i);
}
}*/
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 (size_t i = 0; i < n; ++i)
{
if (_matrix[srci][i] != MAX_W)
{
minq.push(Edge(srci, i, _matrix[srci][i]));
}
}
cout << "Prim开始选边" << endl;
size_t size = 0;
W totalW = W();
while (!minq.empty())
{
Edge min = minq.top();
minq.pop();
// 最小边的目标点也在X集合，则构成环
if (X[min._dsti])
{
//cout << "构成环:";
//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
}
else
{
minTree._AddEdge(min._srci, min._dsti, min._w);
//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
X[min._dsti]= true;
Y[min._dsti] = false;
++size;
totalW += min._w;
if (size == n - 1)
break;
for (size_t 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 (size == n - 1)
{
return totalW;
}
else
{
return W();
}
}
两种方法对比
- Prim算法构造最小生成树的思想在选边时是不需要判环，但上述利用优先级队列实现的过程中仍需判环，如果在每次选边的时候能够通过某种方式，从连接 forest 集合和 remain 集合的所有边中选出权值最小的边，那么就无需判环，但这两个集合中的顶点是不断在变化的，每次选边时都遍历连接两个集合的所有边，该过程的时间复杂度较高(达到O(N^3)的级别)，所以我们采用 vector< bool > 的方法来表示两个集合，进而解决了判环的问题。
- Kruskal算法本质是一种全局的贪心，每次选边时都是在所有边中选出权值最小的边，而Prim算法本质是一种局部的贪心，每次选边时是从连接 forest 集合和 remain 集合的所有边中选出权值最小的边。
总结
困了，接下来还有最短路径问题，就等早上起来再写吧！