最小生成樹 《啊哈算法》讀書筆記

最小生成樹：任何隻由G的邊構成,并包含G的所有頂點的樹稱為G的生成樹(G連通). 權重無向圖G的生成樹的代價是該生成樹的所有邊的代碼(權)的和. 最小代價生成樹是其所有生成樹中代價最小的生成樹。

  假設WN=(V,{E})是一個含有n個頂點的連通網，則按照克魯斯卡爾算法構造最小生成樹的過程為：先構造一個隻含n個頂點，而邊集為空的子圖，若将該子圖中各個頂點看成是各棵樹上的根結點，則它是一個含有n棵樹的一個森（摘自  nocow）         

  求最小生成樹的主要算法:Kruskal算法     Prim算法

Kruskal算法（克魯斯卡爾算法）：（如果想要邊的總長度之和最短，我們自然可以想到首先先選最短的邊）将所有的邊排序，從最小的邊開始選，每次連通最小的邊，不能形成回路，是以就要求判斷兩點間是否已經連通。為了優化操作，我們這裡用并查集優化，判斷其是否在一個樹上。如果不在一個樹上，就加進去，繼續添加。

  時間複雜度為O(MlogM)

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

struct edge
{
    int u;
    int v;
    int w;
}e[10];
int n,m;
int f[7]={0},sum=0,counter=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;
            //swap(e[i],e[j]);
        }
    }
    //基準歸位
    t = e[left];
    e[left]= e[i];
    e[i] = t;
    //swap(e[left],e[i]);
    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];
    }
}

bool merge(int v,int u)
{
    int t1,t2;//t1,t2分别為v和u的boss，每次都是用boss解決
    t1=getf(v);
    t2=getf(u);
    if(t1!=t2)
    {
        f[t2] = t1;//靠左原則
        return 1;
        //路徑壓縮後，将f[u]的根值夜指派為v的祖先f[t1]
    }
    return 0;
}
int main()
{
    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);

    quicksort(1,m);

    //并查集優化
    for(int i=1;i<=n;i++)
        f[i]=i;

    //Kruskal算法核心部分
    for(int i=1;i<=m;i++)//枚舉
    {
        //判斷一條邊的兩個頂點是否連通，即是否在一個集合中
        if(merge(e[i].u,e[i].v))
        {
            counter++;
            sum+=e[i].w;
        }
        if(counter == n-1)
            break;
    }
    printf("%d\n",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
*/
           

然後看到NOCOW上的超級精簡代碼，順便貼上吧

的

/*使用Union-Find判斷是否在一個集合，代碼比較STL-style
	Author:YangZX*/
#include <iostream>
#include<algorithm>
using namespace std; const
int MAXV = 1024, MAXE = 100001;
int n, m, f[MAXV], ans, cnt;
struct edge
{
      int f, t, w;
}es[MAXE];
bool cmp(const edge &a, const edge &b)
{
     return a.w < b.w;
}
void Fill(int &a)
{
    static int cnt = 0; a = ++cnt;
}
int get(int x)
{
    return x == f[x] ? x : f[x] = get(f[x]);
}
void Kruskal(const edge &e)
{ if(get(e.f) != get(e.t))
    {
        f[get(e.f)] = get(e.t); ans += e.w; cnt++;
    }
}
void Read(edge &e)
{
     cin>>e.f>>e.t>>e.w;
}
int main()
{
    cin>>n>>m;
    for_each(es+1, es+m+1, Read);
    make_heap(es+1, es+m+1, cmp);
    sort_heap(es+1, es+m+1, cmp);
    for_each(f+1, f+n+1, Fill);
    for_each(es+1, es+m+1, Kruskal);
    cout<<(cnt < n-1 ? -1: ans)<<endl;
    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
*/
           

Prim算法（普裡姆算法） ：選中任意一個頂點，将其加入到生成樹中去（這裡假設為頂點1）。用數組記錄生成樹到各個頂點的距離，每次都是這樣。從數組中選出離生成樹最近的頂點加入到生成樹中（這裡用的dijkstra的思想），用dis數組更新為生成樹到每一個不在生成樹中的頂點的距離（松弛），重複直到有了n個頂點為止。

代碼：

#include<iostream>
#include<cstdio>
using namespace std;

const int INF = 99999999;
int e[7][7],dis[7],book[7]={0};
int main()
{
    int n,m;
    int counter = 0,sum = 0;
    scanf("%d%d",&n,&m);

    //初始化
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++)
            if(i == j)  e[i][j] = 0;
                else    e[i][j] = INF;

        int t1,t2,t3;
        for(int i = 1;i <= m;i++)
        {
            scanf("%d%d%d",&t1,&t2,&t3);
            e[t1][t2] = e[t2][t1] = t3;//無向圖
        }

        //初始化dis數組
        for(int i = 1;i <= n;i++)
            dis[i] = e[1][i];

        //Prim算法核心
        //将1号頂點加入生成樹
        book[1] = 1;
        counter++;
        int u,v,minn;
        while(counter < n)
        {
            minn = INF;
            for(int i = 1;i <= n;i++)
            {
                if(!book[i] && dis[i] < minn)
                {
                    minn = dis[i];
                    u = i;
                }
            }

            book[u] = 1;
            counter++;
            sum += dis[u];
            for(int v = 1;v <= n;v++)
            {
                if(!book[v] && dis[v] > e[u][v])
                   dis[v] = e[u][v];
            }
        }
        printf("%d\n",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
*/
           

堆優化後的代碼：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int INF = 99999999;
const int N = 100;
int dis[N],book[N]={0};
int h[N],pos[N],size;

void swap(int x,int y)
{
    int t;
    t = h[x];
    h[x] = h[y];
    h[y] = t;

    t = pos[h[x]];
    pos[h[x]] = pos[h[y]];
    pos[h[y]] = t;
}

void siftdown(int i)
{
    int t,flag = 0;
    while(i*2 <= size &&flag == 0)
    {
        if(dis[h[i]] > dis[h[i*2]])
            t=2*i;
        else
            t = i;

        //如果它有左兒子，再對右兒子進行讨論
        if(i*2+1 <= size)
        {
            if(dis[h[t]] > dis[h[i*2+1]])
                t = i*2+1;
        }
        //如果發現最小的節點編号不是自己，說明子節點中有更小的
        if(t!=i)
        {
            swap(t,i);
            i = t;
        }
        else
            flag = 1;
    }
}

void siftup(int i)
{
    int flag = 0;
    if(i == 1)
        return;
    while(i!=1 && flag == 0)
    {
        if(dis[h[i]] < dis[h[i/2]])
            swap(i,i/2);
        else
            flag = 1;
        i/=2;
    }
}

int pop()
{
    int t;
    t = h[1];
    pos[t] = 0;
    h[1] = h[size];
    pos[h[1]] = 1;
    size--;
    siftdown(1);
    return t;
}
int main()
{
    int n,m,k;
    int u[N],v[N],w[N],first[N],next[N];
    int counter = 0,sum = 0;
    scanf("%d%d",&n,&m);

    //讀入邊
    for(int i = 1;i <= m;i++)
        scanf("%d%d%d",&u[i],&v[i],&w[i]);

        //無向圖
        for(int i = m+1;i <= 2*m;i++)
        {
            u[i] = v[i-m];
            v[i] = u[i-m];
            w[i] = w[i -m];
        }

        //鄰接表儲存邊
        for(int i = 1;i <= m;i++)
            first[i] = -1;
        for(int i = 1;i <= 2*m;i++)
        {
            next[i] = first[u[i]];
            first[u[i]] = i;
        }

        //Prim算法核心
        //講1号頂點加入生成樹
        counter++;
        book[1] = 1;

        //初始化dis數組，這裡是1号頂點到其餘各頂點的初始距離
        dis[1] = 0;
        for(int i = 2;i <= n;i++)
            dis[i] = INF;
            k = first[1];
            while(k != -1)
            {
                dis[v[k]] = w[k];
                k = next[k];
            }

            //初始化堆
            size = n;
            for(int i = 1;i <= size;i++)
            {
                h[i] = i;
                pos[i] = i;
            }
            for(int i = size/2;i >= 1;i--)
            {
                siftdown(i);
            }
            pop();//先彈出一個堆頂的元素，因為此時堆頂是1号頂點
            int j;
            while(counter < n)
            {
                j = pop();
                book[j] = 1;
                counter++;
                sum += dis[j];

                //掃描目前頂點j所有的邊，再以j為中間節點，進行松弛
                k = first[j];
                while(k != -1)
                {
                    if(book[v[k]]==0&&dis[v[k]] > w[k])
                    {
                        dis[v[k]] = w[k];
                        siftup(pos[v[k]]);//對該點再堆中進行向上調整
                    }
                    k = next[k];
                }
            }
            printf("%d\n",sum);
}