題注
《面試寶典》有相關習題，但思路相對不清晰，排版有錯誤，作者對此參考相關書籍和自己觀點進行了重寫，供大家參考。
最小生成樹——包含帶權圖中的全部頂點并不能形成環，且權值之和最小的圖。
求解最小生成樹的方法包括：Prim算法和Kruskal算法。
對于Prim算法思想：1）從源結點集中標明一個源結點（初始源節點集合中隻有設定一個結點）；2）從剩餘結點中選擇與源節點集有連接配接的且權值最小的邊。将該源節點加入源節點集合中。然後疊代執行1），2）。
如下圖的圖結構，含有7個頂點，下圖示為圖的鄰接矩陣存儲結構。
模拟執行步驟如下：
前提：源節點集合VertexSet中初始隻有設定的0（假定，可以任意取0à6中任意值）。起初初始的邊結合EdgeSet為空。
步驟 1：從與0相連的邊集合中，標明權值最小的邊，對應上圖Vertex0行顯然為2。是以選擇的頂點為Vertex3。
| VertexSet | EdgeSet | SumWeight |
|---|---|---|
| 0,3 | （0,3） | 2 |
步驟 2：從與{0,3}相連的邊集合中，標明權值最小的邊，如下圖，顯然權值為5。是以選擇的頂點為Vertex2。
集合變為：
| 0,3,2 | （0,3）(0,2) | 2+5 |
步驟 3：從與{0,3,2}相連的邊集合中，標明權值最小的邊，如下圖，顯然權值為4。是以選擇的頂點為Vertex6。
| 0,3,2,6 | （0,3）(0,2)（2,6） | 2+5+5 |
步驟4：從與{0,3,2,6}相連的邊集合中，標明權值最小的邊，如下圖，顯然權值為5。是以選擇的頂點為Vertex1。
| 0,3,2,6,1 | （0,3）(0,2)（2,6）(6,1) | 2+5+5+4 |
步驟5：從與{0,3,2,6,1}相連的邊集合中，標明權值最小的邊，如下圖，顯然權值為2。是以選擇的頂點為Vertex4。
| 0,3,2,6,1,4 | （0,3）(0,2)（2,6）(6,1)（1,4） | 2+5+5+4+2 |
步驟6：從與{0,3,2,6,1,4}相連的邊集合中，標明權值最小的邊，如下圖，顯然權值為2。是以選擇的頂點為Vertex4。
| 0,3,2,6,1,4,5 | 2+5+5+4+2+7 |
最後：周遊後的結果如下2圖：即包含所有頂點，沒有環路，且權值最小。
| （0,3）(0,2)（2,6）(6,1)（1,4）(2,5) | 2+5+5+4+2+7=25 |
//inifinity 代表權值無窮大，即不可達。
int g_WeightMatrix[7][7] ={0,6,5,2,infinity,infinity,infinity,
6,0,infinity,infinity,2,infinity,4,
5,infinity,0,infinity,infinity,7,5,
2,infinity,infinity,0,8,infinity,infinity,
infinity,2,infinity,8,0,10,infinity,
infinity,infinity,7,infinity,10,0,infinity,
infinity,4,5,infinity,infinity,infinity,0};
template<class vType, int size>
class msTreeType : publicgraphType<vType, size>
{
public:
voidcreateSpanningGraph();
voidminimalSpanning(vType sVertex);
voidprintTreeAndWeight();
protected:
vTypesource; //
intweights[size][size]; //權重數組
intedges[size]; //邊的集合,edges[0]=5即代表0-5之間有邊存在。
intedgeWeights[size]; //存儲從某頂點開始的權重.
}; 1.建立權重圖
建立權重圖的時候，我們做了簡化處理。隻是将給定的權重數組指派過來了。[此處稍作修改，便可以改為手動輸入頂點及鄰接邊的關系]。圖的存儲形式：鄰接矩陣存儲！
template <class vType, int size>
voidmsTreeType<vType,size>::createSpanningGraph()
{
gSize= size;
source= 0; //記錄初始點為0.
for(int i = 0; i < size; i++)
{
for(int j =0; j < size; j++)
{
weights[i][j]= g_WeightMatrix[i][j];
if(weights[i][j]!= 0 && weights[i][j] != infinity)
{
edges[i]= j; //代表i--j之間的連線存在
// cout << "edges[ " <<i << " ]=" << edges[i] << "\t";
}
cout<< weights[i][j] << "\t";
}
cout<< endl;
}
} 2.最小生成樹
1.巧妙的記錄源結點、目标結點的方法(通過數組下标和結果值）；2.還需要存儲每次比較後的最小的權重值。
template <class vType, int size>
voidmsTreeType<vType,size>::minimalSpanning(vType sVertex)
{
vType startVertex, endVertex;
int minWeight;
source = sVertex;
//代表mstree的結點結合中是否存在點. mstv[5] =true,代表結點5在集合中已經存在。
//=false,則代表不存在.
bool mstv[size];
//初始化 0代表到自身, infinity代表不可達.
for(int j = 0; j < gSize; j++)
{
mstv[j]= false;
edges[j]= source;
edgeWeights[j]= weights[source][j];
}
mstv[source]= true;
edgeWeights[source]= 0; //初始設定
for(int i = 0; i < gSize-1; i++)
{
minWeight= infinity;
//從所有頂點中尋找權重最小且未被辨別的頂點,v記錄該頂點,minWeight記錄權重值。
for(int j = 0; j < gSize; j++)
{
if(mstv[j])//mstv中已經存在的點j
{
for(intk=0; k < gSize; k++)
{
//尋找由已經存在的結點中到剩餘結點權值最小的邊。
if(!mstv[k]&& weights[j][k] < minWeight)
{
endVertex= k; //目的
startVertex= j; //源
minWeight= weights[j][k]; //最小權重
}
}//endfor k
}//endif(mstv[j])
}//endfor j
mstv[endVertex]= true;
edges[endVertex]= startVertex;
edgeWeights[endVertex]= minWeight;
}//endfor
} 3.列印小生成樹
template <class vType, int size>
voidmsTreeType<vType,size>::printTreeAndWeight()
{
inttreeWeight = 0;
minimalSpanning(source);
cout<< "Source vertex: " << source << endl;
cout<< "Edges\t\tWeight" << endl;
for(int j = 0; j < gSize; j++)
{
if(edgeWeights[j]!= 0)
{
treeWeight= treeWeight + edgeWeights[j];
cout<< "(" << j << ", " <<edges[j] << ")\t\t"<< edgeWeights[j] << endl;
}
}
cout<< endl;
cout<< "Tree Weight: " << treeWeight << endl;
} 作者：銘毅天下
來源：CSDN
原文：
https://blog.csdn.net/laoyang360/article/details/7905688版權聲明：本文為部落客原創文章，轉載請附上博文連結！