沧州网站制作费用,大众软件回应中国芯片行业最大投资,苏州市网站优化,wordpress自动外链缩略图文章目录 前言一、图的遍历广度优先遍历深度优先遍历 二、最小生成树Kruskal算法Prim算法两种方法对比 总结 前言 承上启下#xff0c;我们来学习下图的中篇#xff01;#xff01;#xff01; 一、图的遍历 图的遍历指的是遍历图中的顶点#xff0c;主要有 广度优先遍历 … 文章目录 前言一、图的遍历广度优先遍历深度优先遍历 二、最小生成树Kruskal算法Prim算法两种方法对比 总结 前言 承上启下我们来学习下图的中篇 一、图的遍历 图的遍历指的是遍历图中的顶点主要有 广度优先遍历 和 深度优先遍历 两种方式。
广度优先遍历 广度优先遍历又称BFS其遍历过程类似于二叉树的层序遍历从起始顶点开始一层一层向外进行遍历。 广度优先遍历的实现
广度优先遍历需要借助一个队列和一个标记数组利用队列先进先出的特点实现一层一层向外遍历利用标记数组来记录各个顶点是否被访问过。刚开始时将起始顶点入队列并将起始顶点标记为访问过然后不断从队列中取出顶点进行访问并判断该顶点是否有邻接顶点如果有邻接顶点并且该邻接顶点没有被访问过则将该邻接顶点入队列并在入队列后立即将该邻接顶点标记为访问过。 void BFS(const V src) {size_t srci GetVertexIndex(src);// 队列和标记数组queueint q;vectorbool 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, vectorbool 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);vectorbool 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 GraphV, 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_queueEdge, vectorEdge, greaterEdge 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);}/*setint X;setint Y;X.insert(srci);for (size_t i 0; i n; i){if (i ! srci){Y.insert(i);}}*/vectorbool X(n, false);vectorbool Y(n, true);X[srci] true;Y[srci] false;// 从X-Y集合中连接的边里面选出最小的边priority_queueEdge, vectorEdge, greaterEdge 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 集合的所有边中选出权值最小的边。 总结 困了接下来还有最短路径问题就等早上起来再写吧
