圖的生成樹就是携丁，在頂點集琢歇，邊集中找到一個集合，里面有n個頂點（所有頂點）梦鉴，n-1條邊李茫，這個集合能組成一棵樹。這便是生成樹肥橙，而最小生成樹是魄宏，這個樹的邊權(quán)之和是所有生成樹最小的。
實現(xiàn)最小生成樹的算法可分為兩種存筏，一種是面向頂點宠互，一種是面向邊，都是貪心算法椭坚。
1. Prim算法（普里姆算法）
面向頂點的算法予跌，基本思路是先讓一個頂點加入樹，然后不斷地把距離樹中頂點最近的且未加入樹的頂點加入樹中善茎。
//lowcost存儲著每一個頂點到當(dāng)前樹的最近距離券册，初始值為，每個頂點到樹的第一個點的最短距離
for (i = 1; i < G.numVertexes;i++)
{
min = INFINITY;
while(j < G.numVertexes)//找出離樹最近且不在樹中的頂點
{
if (lowcost[j] != 0 && lowcost[j] < min)
{
min = lowcost[j];
k = j;
}
}
printf("")//輸出新加入樹中的頂點k
lowcost[k] = 0;//頂點k距離樹的最短距離設(shè)為0垂涯，表示k已在樹中
for (j = 1; j < G.numVertexes; j++)
{
//遍歷所有頂點烁焙，如果他們與新加入頂點k的距離比原來lowcost要短，則刷新lowcost
if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j])
{
lowcost[j] = G.arc[k][j];
}
}
}
2. Kruskal算法 （克魯斯卡爾算法）
面向邊的算法耕赘，基本思路是不斷讓最短的邊加入及其連接的點加入樹中骄蝇。但是，可能會連入邊導(dǎo)致樹出現(xiàn)環(huán)操骡，所以九火，最短邊加入之前要判斷其加入是否會使樹變成圖赚窃。
生成樹的本質(zhì)是一個樹狀的連通圖，而Kruskal算法形成生成樹的過程吃既，就是不斷添加新的邊考榨。
這個過程中，無非出現(xiàn)兩種情況
- 添加新邊鹦倚，樹中多添加了一個頂點
- 添加新邊河质，樹中多添加了一個連通圖（也就是已經(jīng)連好的一連串頂點）
第二種情況可能存在，新添加的頂點所在的連通圖震叙，不是新的連通圖掀鹅，而是同一個連通圖中的兩個點相連形成環(huán)，要想辦法判斷出這種情況媒楼。即新添加的邊的兩個頂點是否存在于同一個連通圖中乐尊。
//所有的parent都初始化為0
int Find (int *parent, int f)
{
while (parent[f] > 0)
f = parent[f];
return f;
}
//邊的數(shù)組是以邊的長度排序的，所以遍歷是從最短邊開始的
for (i = 0; i< G.numEdges; i++)
{
n = Find(parent, edges[i].begin);
m = Find(parent, edges[i].end);
if (n != m)
{
parent[n] = m;
printf()//輸出新加入的邊
}
}
所生成的連通圖的點都以 <1,2>,<2,3><3,4>這樣的序列記錄起來划址。
用的是parent數(shù)組扔嵌，parent[1] = 2,parent[2] = 3,parent[3] = 4的方式。
因此edges[i] 所連的兩個頂點夺颤，如果在同一個連通圖內(nèi)痢缎，必然能通過Find()最終找到在連通圖序列中排行最后的點。所以此時世澜，m == n独旷。
