最小生成樹總結（Prim,Kruskal)

最小生成樹就是用最少的邊讓圖連通

Kruskal:

首先按照邊權進行從小到大進行排序，每次從剩餘的邊中選擇權值最小且邊的兩個頂點不在同一個集合内的邊（就是不會産生回路的邊），加入生成樹中，直到加入了n-1條邊。

代碼：

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=105;//N的數值和邊數有關
struct edge
{
    int u;
    int v;
    int w;
}e[N];
int n,m;
int f[N]={0},sum=0,cnt=0;//并查集用的變量
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;
        }
    }
        t=e[left];
        e[left]=e[i];
        e[i]=t;

        quicksort(left,i-1);
        quicksort(i+1,right);
        return;
}
bool comp(struct edge a,struct edge b)//sort中的比較函數
{
    return a.w < b.w;
}
//并查集找祖先
int getf(int v)
{
    if(f[v]==v)
        return v;
    else
    {
        f[v]=getf(f[v]);
        return f[v];
    }
}
//并查集合并子集
int merge1(int v,int u)
{
    int t1,t2;
    t1=getf(v);
    t2=getf(u);
    if(t1!=t2) //不在生成樹傳回1，并加入生成樹
    {
        f[t2]=t1;
        return 1;
    }
    return 0;
}


int main()
{
    int i;
    scanf("%d %d",&n,&m);
    cnt=0,sum=0;
    for(i=1; i<=m; i++)
        scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w);
    quicksort(1,m);//快速排序
   //sort(e+1,e+m+1,comp);//算法的快排

    for(i=1; i<=n; i++)
    {
        f[i]=i;
    }

    for(i=1; i<=m; i++)
    {
        if( merge1(e[i].u,e[i].v) )
        {
            cnt++;
            sum=sum+e[i].w;
        }
        if(cnt == n-1)
            break;
    }

    printf("%d",sum);

    return 0;
}
/*
6 9
2 4 11
3 5 13
4 6 3
5 6 4
2 3 6
4 5 7
1 2 1
3 4 9
1 3 2

ans:19
*/

           

Prim : 圖中頂點分兩類，樹頂點（已加入生成樹），非樹頂點（未加入生成樹)。首先選擇任意頂點加入生成樹，然後找出一條邊加入生成樹，這需要枚舉每個樹頂點到每個非樹頂點是以的邊，然後找到最短邊加入最小生成樹，重複n-1,直到将所有的頂點都加入到生成樹中。

dis[N] 數組用來存放生成樹到個各點的距離。

#include<cstdio>
#include<cstring>
const int N=105;
int main()
{
    int n,m,i,j,k,minn,t1,t2,t3;
    int e[N][N],dis[N],book[N];
    int inf=0x3f3f3f;
    int cnt,sum;

    scanf("%d %d",&n,&m);
    cnt=0,sum=0;
    //圖初始化
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            if(i==j) e[i][j]=0;
            else e[i][j]=inf;
        }
    }

    for(i=1; i<=m; i++)
    {
        scanf("%d %d %d",&t1,&t2,&t3);
        e[t1][t2]=t3;
        e[t2][t1]=t3;
    }
    //dis，book數組初始化
    for(i=1; i<=n; i++)
        dis[i]=e[1][i];
    memset(book,0,sizeof(book));
    book[1]=1;
    cnt++;
    while(cnt<n)
    {
        minn=inf;
        for(i=1; i<=n; i++)
        {
            if(book[i]==0 && dis[i]<minn)
            {
                minn=dis[i];
                j=i;
            }

        }
        book[j]=1; cnt++; sum+=dis[j];
        for(k=1; k<=n; k++)
        {
            if(book[k]==0 && dis[k]>e[j][k])
                dis[k]=e[j][k];
        }
    }

    printf("%d",sum);


    return 0;
}
/*
6 9
2 4 11
3 5 13
4 6 3
5 6 4
2 3 6
4 5 7
1 2 1
3 4 9
1 3 2
*/

           

最小生成樹題目

• HDU-1863 連通，不連通圖的判斷
• HDU-1233 闆子題
• HDU-1879 零一路，存在邊權為0，不存在邊權不變。
• POJ-1251 字母頂點
• POJ-1287 多重邊
• POJ-1258 輸入圖