1.最小生成树算法
定义:最小生成树算法:连通图有n个顶点组成,那么此时的图的每一个点都能相互连接并且边的个数为n-1条,那么此时该图就是最小生成树.
下面量算法有几个共同的特点:
3.n-1条边的图不能存在回路
4.Kruskal和Prim两个算法都采用了逐步求解的贪心策略
1.Kruskal算法
任给一个有n个顶点的连通网络N={V,E},首先构造一个由这n个顶点组成、不含任何边的图G={V,NULL},其中每个顶点自成一个连通分量,其次不断从E中取出权值最小的一条边(若有多条任取其一),若该边的两个顶点来自不同的连通分量,则将此边加入到G中。如此重复,直到所有顶点在同一个连通分量上为止。核心:每次迭代时,选出一条具有最小权值,且两端点不在同一连通分量上的边,加入生成树。
//数组的下标添加边 void _AddEdge(size_t srci, size_t dsti, const W& w) { _matrix[srci][dsti] = w; // 无向图 if (Direction == false) { _matrix[dsti][srci] = w; } } 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 _edge)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])); } } } 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; } } if (size == n - 1) return totalW; else return W(); }
2.Prim算法
2.从集合中找出与源点的边中权重最小的点,从待处理的集合中移除标记为确定的点
4.重复2,3步直到所有的点都被标记
(重点是不需要并查集来判断是否成环,因为两个集合就天然区分是否成环的因素)
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); } vector<bool> X(n, false); vector<bool> Y(n, true); X[srci] = true; Y[srci] = false; priority_queue<Edge, vector<Edge>, greater<Edge>> minq; for (int i = 0; i < n; ++i) { if (_matrix[srci][i] != MAX_W) { minq.push(Edge(srci, i, _matrix[srci][i]); } } size_t num = 0; W sum = W(); while (!minq.empty()) { Edge min = minq.top(); minq.pop(); if (!X[min._dsti]) { minTree.AddEdge(min._srci, min._dsti, min._w); X.insert(min._dsti); Y.erase(min._dsti); ++num; sum += min._w; if (num == 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 (num == n - 1) return sum; else return W(); }
原文地址:https://blog.csdn.net/m0_63488627/article/details/134701336
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_8465.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。