最小生成樹及其構造方法

ps：好久沒寫新文章了，來到了廣州見習，沒有網絡，也不知道這學校怎麼想的！！接下來進入正題

何謂最小生成樹

對于一個帶權連通無向圖G中的不同生成樹，各棵樹的邊上的權值之和可能不同，邊上的權值之和最小的樹稱之為該圖得最小生成樹

構造方法

求圖得最小生成樹的倆個算法，即普利姆算法和克魯斯卡爾算法

普利姆算法(Prim)

在了解普利姆算法之前，先想想我們最開始的目的是什麼？俗氣一點說就是畫路線圖，而且這個路線必須是最短的。

思路

先用抽象一點的語言描述，就是現在我們先拿出圖中的第一個頂點(其實可以是任意頂點)，然後把這個頂點放進集合A中，然後将這個頂點與集合外的頂點連成的線的權值做比較，把那個能連權值最小的線的頂點也放進集合裡面。然後再把集合裡面的倆個頂點與集合外的頂點繼續比較，重複此步驟。可以參考：

第一步:從①開始，①進集合，用與集合外所有頂點能構成的邊中找最小權值的一條邊
①——②權
①——③權 -> 取①——③邊
①——④權



第二步:③進集合，①，③與②,④,⑤,⑥構成的最小邊為
①——④權
③——⑥權 -> 取③——⑥邊

第三步:⑥進集合，①，③,⑥與②,④,⑤構成的各最小邊
①——②權
③——②權
⑥——④權 -> 取⑥——④邊

第四步:④進集合，①，③,⑥,④與②,⑤構成的各最小邊
①——②權
③——②權 -> 取③——②邊
⑥——⑤權

第四步:②進集合，①，③,⑥,②,④與⑤構成的各最小邊
②——⑤權 -> 取②——⑤邊
           

沒錯上面的說法很好，但實際中的代碼跟上面的思想是一樣，但就有點難了解，我們換一種說法，從代碼的角度來分析。

假如我們現在拿到手的是一個鄰接矩陣存儲方法的圖(假設這個圖有n個頂點)

1.那麼首先我們先執行個體化一個數組A，一個數組B。先這麼規定，數組A存儲的是n-1條邊的權值。那麼另外一個數組就是存儲邊的起始頂點。舉個例子A[1]=3,B[1]=4，代表的就是第一個頂點所連接配接的最短的邊的權值是3，然後這條最短邊是和第4個頂點連接配接而成的。

2.那麼有了這倆個數組，事情就變得好辦很多了。B[i]=k代表的就是i與k連接配接可以形成最小權值的邊，而A[i]數組就代表i頂點與這個k(k=B[i])連接配接的邊的那個最小權值。這裡有點繞口。

從實際例子來講思路比較好，先看看下圖：

3.先進行初始化

for(i=;i<g.n;i++)
{
    lowcost[i] = g.edges[][i];
    closest[i] = ;
}
           

此時lowcost數組的意義就是各個頂點到0頂點的距離，closest數組的原理就是目前lowcost中的各個數值是由哪倆個頂點連起來的，可見初始化過程使得closest的每個值都為0，也就是lowcost中的每條邊都是和0頂點連起來的.

4.接下來，取出lowcost中最小的邊，如下：

min = INF;
//先周遊出lowcost裡面最小的拿出來
for(j=;j<g.n;j++)
{
    if(lowcost[j]!= && lowcost[j]<min)
    {
        min = lowcost[j];
        k = j;
    }
}
printf("邊(%d,%d)權為：%d\n",closest[k],k,min);
lowcost[k] = ;
           

取出的這條邊就是頂點0與頂點k連接配接而成的。先用我們的腦子想一下，取出這條最短邊之後我們應該做些什麼事？

5.沒錯，取出第二條最短的邊，我們需要把能和頂點0和頂點k連線的那些邊取出來然後進行比較存儲在lowcost數組中。

這也就跟我們第一個抽象化的思路一樣，頂點0和頂點k在集合裡面，與集合外面的頂點進行比較。

那麼我們該怎麼做這個比較的操作呢？

for(j=0;j<g.n;j++)
{
    if(g.edges[k][j]!=0 && lowcost[j]>g.edges[k][j])
    {5
        lowcost[j] = g.edges[k][j];
        closest[j] = k;
    }
}
           

g.edges[k][j]就是頂點j到頂點k的距離，lowcost[j]就是頂點j到頂點0的目前最短距離(在第一次大循環中，由于closest[j]都等于0，是以都是與頂點0的距離)，拿這倆個數值做比較，得出一個更小的距離存儲到lowcost中。

那麼整個算法就是：

代碼

#define INF ;
void Prim(MGraph g,int v)
{
    int lowcost[MAXV];
    int min;
    //就是對應的元素下标的頂點的連接配接的上一個頂點
    int closest[MAXV];
    int i,k;
    for(i=;i<g.n;i++)
    {
        lowcost[i] = g.edges[v][i];
        closest[i] = v;
    }
    for(i=;i<g.n;i++)
    {
        min = INF;
        //先周遊出lowcost裡面最小的拿出來
        for(j=;j<g.n;j++)
        {
            if(lowcost[j]!= && lowcost[j]<min)
            {
                min = lowcost[j];
                k = j;
            }
        }
        printf("邊(%d,%d)權為：%d\n",closest[k],k,min);
        lowcost[k] = ;
        //接下來做的就是把集合裡的倆個頂點跟集合外的頂點組成的邊的權值做比較
        for(j=;j<g.n;j++)
        {
            if(g.edges[k][j]!= && lowcost[j]>g.edges[k][j])
            {
                lowcost[j] = g.edges[k][j];
                closest[j] = k;
            }
        }
    }
}
           

總結

對于普利姆算法來說，隻要了解lowcost數組和closest數組，基本大概思路就已經清晰了

克魯斯卡爾算法(Kruskal)

克魯斯卡爾算法的思想就是先把所有邊取出來，然後按從小到大排序，每次取出一條邊，判斷是否形成回路，如果是就丢棄，否則這條邊就是我們想要的權值最小的邊。

思路

核心-怎麼樣去判斷回路

在這裡需要簡單地說一下思路。上面已經說了，我們有一個數組是按權值從小到大存儲邊的(這裡先不要去考慮怎麼存儲邊)，然後我們每次拿出來一條邊，這時候就需要判斷這條邊會不會跟我們前面已選擇的邊形成回路，是以，每次取出邊的時候，我們需要把它的“原始頂點”存放到vset數組中，那麼怎麼存放呢？

假設我們現在有邊ab，bc，cd都被取出來。那麼這三條邊就屬于一個連通分量，也就是到時是連在一起的。那麼ad這倆個頂點就不能連接配接起來了，很明顯會構成一個回路，計算機應該怎麼判斷呢。可以這樣規定，ab連在一起了，是以b的parent是a，bc連在一起了，是以c的parent是b，cd連在一起了是以d的parent是c。那麼我們可以通過下面的代碼來判斷是否構成回路：

int Find(int *parent,int f)
{
    while(parnet[f]>)
        f = parent[f]
    return f;
}
           

上面的代碼實作了查找一個連通分量的其實頂點，通過上面的代碼，我們可以知道d

的“原始頂點”是a，a的原始頂點也是a，是以相等，并不能連線。

代碼

是以整個算法就是：

int Find(int *parent,int f)
{
    while(parnet[f]>)
        f = parent[f]
    return f;
}

Typedef struct
{
    int begin;
    int end;
    int weight;
}Edge;

void Kruskal(MGraph g)
{
    Edge E[MaxSize];
    int vset[MaxSize]；
    int i,k,j;
    for(i=;i<g.n;i++)
        for(j=;j<g.n;j++)
            if(g.edges[i][j]!= && g.edges[i][j]!=INF)
            {
                E[k].begin = i;
                E[k].end = j;
                E[k].weight = g.edges[i][j];
                k++;
            }
    InsertSort(E,g.e);//排序
    for(i=;i<g.n;i++) vset[i]=;
    //要區n-1條邊出來 
    k = ;
    //每次取出一條邊，是以要有一個元素記住現在取到第幾條邊了 
    j = ;
    while(k<g.n)
    {
        u1 = E[j].begin;
        u2 = E[j].end;
        sn1 = Find(vset,u1);
        sn2 = Find(vset,u2);
        if(sn1!=sn2)
        {
            vset[sn2] = sn1;
            printf();
            k++;
        }
        j++;
    }
}