目錄

1.最小生成樹算法

1.Kruskal算法

2.Prim算法

1.最小生成樹算法

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

下面量算法有幾個(gè)共同的特點(diǎn):

1.只能使用圖中權(quán)值最小的邊來構(gòu)造生成樹

2.只能使用恰好n-1條邊構(gòu)造生成樹

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

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

1.Kruskal算法

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

		//數(shù)組的下標(biāo)添加邊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.從源點(diǎn)出發(fā)，將所有與源點(diǎn)連接的點(diǎn)加入一個(gè)待處理的集合中

2.從集合中找出與源點(diǎn)的邊中權(quán)重最小的點(diǎn)，從待處理的集合中移除標(biāo)記為確定的點(diǎn)

3.將找到的點(diǎn)按照步驟1的方式處理

4.重復(fù)2，3步直到所有的點(diǎn)都被標(biāo)記

(重點(diǎn)是不需要并查集來判斷是否成環(huán),因?yàn)閮蓚€(gè)集合就天然區(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();}