目錄

1.最小生成樹算法

1.Kruskal算法

2.Prim算法

1.最小生成樹算法

定義:最小生成樹算法:連通圖有n個頂點組成,那么此時的圖的每一個點都能相互連接并且邊的個數(shù)為n-1條,那么此時該圖就是最小生成樹.

下面量算法有幾個共同的特點:

1.只能使用圖中權值最小的邊來構造生成樹

2.只能使用恰好n-1條邊構造生成樹

3.n-1條邊的圖不能存在回路

4.Kruskal和Prim兩個算法都采用了逐步求解的貪心策略

1.Kruskal算法

任給一個有n個頂點的連通網(wǎng)絡N={V,E}，首先構造一個由這n個頂點組成、不含任何邊的圖G={V,NULL}，其中每個頂點自成一個連通分量，其次不斷從E中取出權值最小的一條邊(若有多條任取其一)，若該邊的兩個頂點來自不同的連通分量，則將此邊加入到G中。如此重復，直到所有頂點在同一個連通分量上為止。核心：每次迭代時，選出一條具有最小權值，且兩端點不在同一連通分量上的邊，加入生成樹。

		//數(shù)組的下標添加邊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;elsereturn W();}

2.Prim算法

1.從源點出發(fā)，將所有與源點連接的點加入一個待處理的集合中

2.從集合中找出與源點的邊中權重最小的點，從待處理的集合中移除標記為確定的點

3.將找到的點按照步驟1的方式處理

4.重復2，3步直到所有的點都被標記

(重點是不需要并查集來判斷是否成環(huán),因為兩個集合就天然區(qū)分是否成環(huán)的因素)

		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;elsereturn W();}