第8章第1節-镖局運镖-圖的最小生成樹-Kruskal算法

#include "stdio.h"

struct edge

{

    int u;

    int v;

    int w;

};//為了友善排序，這裡建立了一個結構體用來存儲邊的關系

struct edge e[10];//數組大小根據實際情況來設定，要比m最大值大1

int n,m;

int f[7] = {0},sum = 0,count = 0;//并查集需要用到的一些變量

//f數組大小更具實際情況來設定，要比n的最大值大1

void quicksort(int left,int right)

{

    int i,j;

    struct edge t;

    if(left > right)

    {

        return;

    }

    i = left;

    j = right;

    while(i != j)

    {

        //順序很重要，要先從右邊開始找

        while(e[j].w >= e[left].w && i < j)

        {

            j--;

        }

        //再從左邊開始找

        while(e[i].w <= e[left].w && i < j)

        {

            i++;

        }

        //交換

        if(i < j)

        {

            t = e[i];

            e[i] = e[j];

            e[j] = t;

        }

    }

    //最終将基準數歸為，将left和i交換

    t = e[left];

    e[left] = e[i];

    e[i] = t;

    quicksort(left,i - 1);//繼續處理左邊的，這裡是一個遞歸的過程

    quicksort(i + 1,right);//繼續處理右邊的，這裡是一個遞歸的過程

    return;

}

//并查集尋找祖先的函數

int getf(int v)

{

    if(f[v] == v)

    {

        return v;

    }

    else

    {

        //這裡是路徑壓縮

        f[v] = getf(f[v]);

        return f[v];

    }

}

//并查集合并兩個子集的函數

int merge(int v,int u)

{

    int t1,t2;

    t1 = getf(v);

    t2 = getf(u);

    if(t1 != t2)//判斷兩個點是否在同一個集合中

    {

        f[t2] = t1;

        return 1;

    }

    return 0;

}

//請從此處開始閱讀程式，從主函數開始閱讀程式是一個好習慣

int main()

{

    int i;

    //讀入n和m，n表示頂點個數，m表示邊的條數

    scanf("%d %d",&n,&m);

    //讀入邊，這裡用一個結構體來存儲邊的關系

    for(i = 1;i <= m;i++)

    {

        scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w);

    }

    quicksort(1,m);//按照權值從小到大對邊進行快速排序

    //并查集初始化

    for(i = 1;i <= n;i++)

    {

        f[i] = i;

    }

    //Kruskal算法核心部分

    for(i = 1;i <= m;i++)//開始從小到大枚舉每一條邊

    {

        //判斷一條邊的兩個頂點是否已經連通，即判斷自己是否已經在同一個集合中

        if(merge(e[i].u,e[i].v))//如果目前尚為不連通，則選用這條邊

        {

            count++;

            sum = sum +e[i].w;

        }

        if(count == n - 1)//直到選用了n-1條邊之後退出循環

        {

            break;

        }

    }

    printf("%d\n",sum );//列印結果

    getchar();getchar();

    return 0;

}