百度贴吧有没有做网站的人,知识库wordpress主题,美橙表业手表网站,网络软文投放数据结构 —— 最小生成树 什么是最小生成树Kruskal算法Prim算法 今天我们来看一下最小生成树#xff1a;
我们之前学习的遍历算法并没有考虑权值#xff0c;仅仅就是遍历结点#xff1a; 今天的最小生成树要满足几个条件#xff1a; 考虑权值所有结点联通权值之和最小无环… 数据结构 —— 最小生成树 什么是最小生成树Kruskal算法Prim算法 今天我们来看一下最小生成树
我们之前学习的遍历算法并没有考虑权值仅仅就是遍历结点 今天的最小生成树要满足几个条件 考虑权值所有结点联通权值之和最小无环 什么是最小生成树
最小生成树Minimum Spanning Tree简称MST是指在一个加权的、无向的连通图中由所有顶点构成的一个子图这个子图是一棵树并且其所有边的权重之和最小。换句话说最小生成树是在保证图中所有顶点连通的前提下使得连接这些顶点的边的总成本最低的一棵树。 最小生成树具有以下特性 它包含图中的所有顶点。它是一个没有环的连通子图即树。它的边数比顶点数少一对于 n 个顶点的图有 n-1 条边。它的边的总权重是所有可能生成树中最小的。 最小生成树在很多实际应用中都有重要作用例如在设计电信网络时为了连接多个地点而需要铺设电缆或光纤最小生成树可以用来确定一种成本最低的铺设方案。
求解最小生成树的常用算法包括 Kruskal算法此算法通过不断选择权重最小的边来构建最小生成树同时避免添加会导致环路形成的边。它通常利用并查集Disjoint Set Union数据结构来检测环路。Prim算法此算法从任意一个顶点开始逐步将顶点及其权重最小的连接边加入到生成树中直到所有顶点都被包含进来。Prim算法可以使用优先队列Priority Queue来高效地选择下一个应加入的边。 我们今天就来介绍一下这两种算法
Kruskal算法
Kruskal算法简单来说就是把所有边拿出来从小到大挑边构成最小生成树
Kruskal算法是一种用于寻找加权、无向连通图的最小生成树Minimum Spanning Tree, MST的贪心算法。它的核心思想是在不形成任何环路的情况下选择权重最小的边来构建生成树直到所有的顶点都被包含在树中。
以下是Kruskal算法的主要步骤 排序边将图中所有的边按照权重从小到大排序。初始化森林创建一个森林其中每个顶点都是一个单独的树即每个顶点都是一个独立的连通分量。选择边遍历排序后的边列表。对于每条边检查它的两个端点是否已经在同一棵树中即是否属于同一个连通分量。如果不是将这条边添加到最小生成树中并将这两个顶点所在的树合并成一棵更大的树。重复步骤3继续选择满足条件的边直到最小生成树中包含了图中的所有顶点或者已经选择了n-1条边其中n是顶点的数量。 Kruskal算法的关键在于能够快速地检测边的两个端点是否属于同一棵树这通常是通过使用并查集Union-Find数据结构来实现的。并查集允许我们在对数时间内执行“查找”操作确定顶点所属的树和“合并”操作将两棵树合并成一棵树。
// 使用Kruskal算法计算最小生成树的总权重
W Kruskal(Self minTree) // Self应为当前类的引用minTree是用于存储最小生成树的实例
{// 初始化最小生成树的顶点集和索引minTree._vertex _vertex;minTree._index _index;minTree._matrix.resize(_vertex.size()); // 创建一个邻接矩阵用于存储最小生成树中的边的权重for (auto e : minTree._matrix) // 将邻接矩阵的所有元素初始化为最大权重值MAX_W{e.resize(_vertex.size(), MAX_W);}// 创建一个优先级队列用于存储边的信息priority_queueEdge, vectorEdge, greaterEdge pq;// 将所有边除了自环和重复边加入优先级队列for (size_t i 0; i _vertex.size(); i) {for (size_t j 0; j _vertex.size(); j) {if (i j _matrix[i][j] ! MAX_W) // 确保不加入自环和重复边{pq.push(Edge(i, j, _matrix[i][j])); // 将边加入优先级队列}}}// 初始化变量用于记录最小生成树的总权重和边的数量W total W();int size 0;UnionFindSet ufs(_vertex.size()); // 创建并查集用于判断顶点是否已经连接while (!pq.empty()) // 当优先级队列非空时{Edge min pq.top(); // 取出权重最小的边pq.pop(); // 移除已取出的边// 判断边的两个顶点是否已经在同一集合内即是否已经连接if (!ufs.InSet(min._srci, min._desi)) {cout _vertex[min._srci] - _vertex[min._desi] : _matrix[min._srci][min._desi] endl; // 打印边的信息minTree._AddEdge(min._srci, min._desi, min._w); // 将边加入最小生成树total min._w; // 更新最小生成树的总权重ufs.Union(min._srci, min._desi); // 合并两个顶点所在的集合size; // 增加边的数量}}cout endl;minTree.Print(); // 打印最小生成树// 如果边的数量等于顶点数量减一则返回最小生成树的总权重if (size _vertex.size() - 1){return total;}else{return W(); // 否则返回默认权重值可能表示无法形成最小生成树}
}我们可以来测试一下 void TestGraph2(){string a[] {海皇,高斯,小傲,小潮,胖迪,小杨,皖皖};Graphstring, int,INT_MAX, false g1(a, sizeof(a)/sizeof(a[0]));g1.AddEdge(小潮, 小傲, 30);g1.AddEdge(小潮, 高斯, 83);g1.AddEdge(小潮, 海皇, 34);g1.AddEdge(胖迪, 海皇, 78);g1.AddEdge(胖迪, 小傲, 76);g1.AddEdge(小杨, 皖皖, 54);g1.AddEdge(小杨, 高斯, 48);g1.Print();cout endl;Graphstring, int, INT_MAX, false kminTree;cout Kruskal: g1.Kruskal(kminTree) endl;}按照Kruskal算法构建出来的图是这样的 胖迪和海皇的关系被抹除了其实我们之前的图里有环
Kruskal算法的时间复杂度主要取决于排序边的操作和并查集的效率。在最好的情况下排序边的时间复杂度为O(E log E)其中E是边的数量并查集操作的时间复杂度接近常数因此整个算法的时间复杂度近似为O(E log E)。由于排序的主导作用该算法适用于边的数量远小于顶点数量平方的图即稀疏图。
Prim算法
Prim算法和上面的思想差不多但是Prim算法会从一个顶点开始这里我假设是从小潮开始 跟小潮连接的3条边会进入优先级队列维护起来 接下来会选择30的权重来构造然后30这条边的另一边的小傲的边入优先级队列 以此类推
// 使用Prim算法构建并返回最小生成树的总权重
W Prim(Self minTree, const V vertex) // Self应该是当前类的引用minTree是用于存储最小生成树的实例vertex是顶点的容器
{// 初始化最小生成树的顶点集和索引minTree._vertex _vertex;minTree._index _index;minTree._matrix.resize(_vertex.size()); // 创建一个邻接矩阵用于存储最小生成树中的边的权重// 初始化邻接矩阵的所有元素为最大权重值MAX_Wfor (auto e : minTree._matrix){e.resize(_vertex.size(), MAX_W);}// 区分顶点集合已选择和未选择size_t srcIndex FindSrci(vertex); // 找到起始顶点的索引vectorbool select(_vertex.size(), false); // 已选择顶点集合初始时所有顶点都未选择vectorbool non_select(_vertex.size(), true); // 未选择顶点集合初始时所有顶点都未被选择select[srcIndex] true; // 起始顶点被标记为已选择non_select[srcIndex] false; // 起始顶点从未选择集合中移除// 创建一个优先级队列用于存储待处理的边priority_queueEdge, vectorEdge, greaterEdge pq; // 边按权重从小到大排序// 将起始顶点的邻接边加入优先级队列for (int i 0; i _vertex.size(); i){if (_matrix[srcIndex][i] ! MAX_W) // 如果存在边且不是最大权重表示边存在{pq.push(Edge(srcIndex, i, _matrix[srcIndex][i])); // 加入边信息到优先级队列}}// 初始化计数器和总权重size_t size 0;W total W(); // 初始化总权重为0// 当优先级队列非空时while (!pq.empty()){Edge min pq.top(); // 获取当前权重最小的边pq.pop(); // 从队列中移除已处理的边// 如果目标顶点已被选择跳过这条边if (select[min._desi]) continue;// 输出边的信息cout _vertex[min._srci] - _vertex[min._desi] : _matrix[min._srci][min._desi] endl;// 添加边到最小生成树minTree._AddEdge(min._srci, min._desi, min._w);// 标记目标顶点为已选择select[min._desi] true;non_select[min._desi] false;size; // 已处理的边数量加1total min._w; // 更新总权重// 将新加入顶点的邻接边加入优先级队列for (size_t i 0; i _vertex.size(); i){if (_matrix[min._desi][i] ! MAX_W non_select[i]) // 如果存在边且目标顶点未被选择{pq.push(Edge(min._desi, i, _matrix[min._desi][i])); // 加入边信息到优先级队列}}}// 打印最小生成树minTree.Print();// 如果边的数量等于顶点数量减一则返回最小生成树的总权重if (size _vertex.size() - 1){return total;}else{return W(); // 否则返回默认权重值可能表示无法形成最小生成树}
}void TestGraph2(){string a[] {海皇,高斯,小傲,小潮,胖迪,小杨,皖皖};Graphstring, int,INT_MAX, false g1(a, sizeof(a)/sizeof(a[0]));g1.AddEdge(小潮, 小傲, 30);g1.AddEdge(小潮, 高斯, 83);g1.AddEdge(小潮, 海皇, 34);g1.AddEdge(胖迪, 海皇, 78);g1.AddEdge(胖迪, 小傲, 76);g1.AddEdge(小杨, 皖皖, 54);g1.AddEdge(小杨, 高斯, 48);g1.Print();cout endl;Graphstring, int, INT_MAX, false kminTree;cout Kruskal: g1.Kruskal(kminTree) endl;cout endl;Graphstring, int, INT_MAX, false pminTree;cout Prim: g1.Prim(pminTree,小潮) endl;}Prim算法同样是用于寻找加权无向图的最小生成树(Minimum Spanning Tree, MST)的一种贪心算法。与Kruskal算法不同的是Prim算法从一个顶点开始逐步添加最短的边来扩展树直到包含所有的顶点。
Prim算法基本步骤 选择任意一个顶点作为起始顶点。在当前树的顶点的邻接边中找到权重最小的边将这条边添加到树中并将新的顶点也添加进来。重复步骤2直到树包含所有的顶点。 这是两种算法挑选边的过程和最后结果大家可以类比对比 //Kruskal算法W Kruskal(Self minTree){//初始化minTree._vertex _vertex;minTree._index _index;minTree._matrix.resize(_vertex.size());for (auto e : minTree._matrix){e.resize(_vertex.size(), MAX_W);}//优先级队列priority_queueEdge, vectorEdge, greaterEdge pq;for (size_t i 0; i _vertex.size(); i){for (size_t j 0; j _vertex.size(); j){if (i j _matrix[i][j] ! MAX_W){pq.push(Edge(i, j, _matrix[i][j]));}}}//拿边构造最小生成树W totoal W();int size 0;UnionFindSet ufs(_vertex.size());while (!pq.empty()){Edge min pq.top();//出边pq.pop();//判断是否在同一集合if (!ufs.InSet(min._srci ,min._desi)){cout _vertex[min._srci] - _vertex[min._desi] : _matrix[min._srci][min._desi] endl;minTree._AddEdge(min._srci, min._desi, min._w);totoal min._w;//合并ufs.Union(min._srci, min._desi);size;}}cout endl;minTree.Print();if (size _vertex.size() - 1){return totoal;}else{return W();}}W Prim(Self minTree,const V vertex){//初始化minTree._vertex _vertex;minTree._index _index;minTree._matrix.resize(_vertex.size());for (auto e : minTree._matrix){e.resize(_vertex.size(), MAX_W);}//区分集合size_t srcIndex FindSrci(vertex);vectorbool select(_vertex.size(), false);vectorbool non_select(_vertex.size(), true);select[srcIndex] true;non_select[srcIndex] false;//开始入边priority_queueEdge, vectorEdge, greaterEdge pq;for (int i 0; i _vertex.size(); i){if (_matrix[srcIndex][i] ! MAX_W){pq.push(Edge(srcIndex, i, _matrix[srcIndex][i]));}}size_t size 0;W totoal W();while (!pq.empty()){Edge min pq.top();pq.pop();if (select[min._desi])continue;cout _vertex[min._srci] - _vertex[min._desi] : _matrix[min._srci][min._desi] endl;minTree._AddEdge(min._srci, min._desi, min._w);select[min._desi] true;non_select[min._desi] false;size;totoal min._w;//新入的顶点的边也加入到优先级队列for (size_t i 0; i _vertex.size(); i){if (_matrix[min._desi][i] ! MAX_W non_select[i]){pq.push(Edge(min._desi, i, _matrix[min._desi][i]));}}}minTree.Print();if (size _vertex.size() - 1){return totoal;}else{return W();}}
