最小生成树笔记

无聊了再坑一坑图论吧。。。啥都搞不好。。。

给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树。。。

有两种著名的算法。。。prim，kruskal。。。

prim的效率取决于优先队列的实现与图的存储方式，这里记顶点数v，边数e 邻接矩阵:O(v²)、邻接表:O(elog₂v)，若用斐波那契堆作为优先队列则效率为O(e+vlog₂v)

kruskal的效率取决于并查集的实现，若用按秩合并与路径压缩效率为O(elog₂e)

[hermit auto=”0″ loop=”1″ unexpand=”0″ fullheight=”0″]netease_songs#:139774[/hermit]
1、prim算法

1.算法简介

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。（来自度娘）

2.算法过程：

(1 将一个图的顶点分为两部分，一部分是最小生成树中的结点（U集合），另一部分是未处理的结点（V集合）。

(2 首先选择一个结点，将这个结点加入U中，作为树根。

(3 对集合U中的顶点所连的边遍历，找出边权值最小的那个，将此边所连顶点从V中删除，加入集合U中。

(4 递归重复步骤3，直到V集合中的结点为空，结束此过程。

(5 U集合中的结点就是由Prime算法得到的最小生成树的结点，依照步骤3的结点连接这些顶点，得到的就是这个图的最小生成树。

3.图像演示

4、动态图演示

5.简单证明prim算法

反证法：假设prim生成的不是最小生成树

1).设prim生成的树为G0

2).假设存在Gmin使得cost(Gmin)<cost(G0)   则在Gmin中存在<u,v>不属于G0

3).将<u,v>加入G0中可得一个环，且<u,v>不是该环的最长边(这是因为<u,v>∈Gmin)

4).这与prim每次生成最短边矛盾

5).故假设不成立，命题得证.

6、代码实现

伪代码

MST-PRIM(G, w, r)
　　　　for each u∈V
　　　　　　do key[u] ← ∞
　　　　　　　  parent[u]← NIL
　　　　key[r] ← 0
　　　　Q ← V
　　　　while Q ≠∅
　　　　　　do u ← EXTRACT-MIN(Q)
　　　　　　　　for each v∈Adj[u]
　　　　　　　　　　do if v∈Q and w(u, v) < key[v]
　　　　　　　　　　　　then parent[v] ← u
　　　　　　　　　　　　　　  key[v] ← w(u, v)

其工作流程为：

（1）首先进行初始化操作，将所有顶点入优先队列，队列的优先级为权值越小优先级越高

（2）取队列顶端的点u，找到所有与它相邻且不在树中的顶点v，如果w(u, v) < key[v]，说明这条边比之前的更优，加入到树中，即更改父节点和key值。这中间还隐含着更新Q的操作（降key值）

（3）重复2操作，直至队列空为止。

（4）最后我们就得到了两个数组，key[v]表示树中连接v顶点的最小权值边的权值，parent[v]表示v的父结点。

现在呢，我们发现一个问题，这里要用到优先队列来实现这个算法，而且每次搜索邻接表都要进行队列更新的操作。

不管用什么方法，总共用时为O(VT(EXTRACTION)+ET(DECREASE))

（1）如果用数组来实现，总时间复杂度为O(V²)

（2）如果用二叉堆来实现，总时间复杂度为O(ElogV)

（3）如果使用斐波那契堆，总时间复杂度为O(E+VlogV)

邻接表实现

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

typedef struct
{
    long v;
    long next;
    long cost;
}Edge;

typedef struct
{
    long v;
    long cost;
}node;


bool operator <(const node &a,const node &b)
{
    return a.cost>b.cost;
}

priority_queue<node> q;

const long MAXN=10000;

Edge e[MAXN];
long p[MAXN];
bool vist[MAXN];

long m,n;
long from,to,cost;

void init()
{
    memset(p,-1,sizeof(p));
    memset(vist,0,sizeof(vist));

    while (!q.empty())
    {
        q.pop();
    }

    long i;
    long eid=0;
    for (i=0;i<n;++i)
    {
        scanf("%ld %ld %ld",&from,&to,&cost);

        e[eid].next=p[from];
        e[eid].v=to;
        e[eid].cost=cost;
        p[from]=eid++;

        //以下适用于无向图

        swap(from,to);

        e[eid].next=p[from];
        e[eid].v=to;
        e[eid].cost=cost;
        p[from]=eid++;

    }
}

void print(long cost)
{
    printf("%ld\n",cost);
}


void Prime()
{
    long cost=0;

    init();
    node t;

    t.v=from;//选择起点
    t.cost=0;

    q.push(t);


    long tt=0;

    while (!q.empty()&&tt<m)
    {
        t=q.top();
        q.pop();

        if (vist[t.v])
        {
            continue;
        }

        cost+=t.cost;
        ++tt;

        vist[t.v]=true;

        long j;
        for (j=p[t.v];j!=-1;j=e[j].next)
        {
            if (!vist[e[j].v])
            {
                node temp;
                temp.v=e[j].v;
                temp.cost=e[j].cost;
                q.push(temp);
            }
        }
    }

    print(cost);
}

int main()
{
    while (scanf("%ld %ld",&m,&n)!=EOF)
    {
        Prime();
    }
    return 0;
}

邻接矩阵

#include <iostream>
#include <cmath>
using namespace std;
#define MAX 99999
#define LEN 101
int dist[LEN];
int map[LEN][LEN];
bool vis[LEN];
void init() {//初始化
    int i,j;
    for(i=0; i<LEN; i++) {
        for(j=0; j<LEN; j++) {
            if(i==j) map[i][j]=0;   //对a[][]进行初始化，一般都要；
           else map[i][j]=MAX;
        }
    }
}
//prim算法
int prim(int n) {
    int i,j,min,pos;
    int sum=0;
    memset(vis,false,sizeof(vis));//初始化
    for(i=1; i<=n; i++) {
        dist[i]=map[1][i];
    }//从1开始
    vis[1]=true;
    dist[1]=MAX;
    //找到权值最小点并记录下位置
    for(i=1; i<n; i++) {
        min=MAX;
        //pos=-1;
        for(j=1; j<=n; j++) {
            if(!vis[j] && dist[j]<min) {
                min=dist[j];
                pos=j;
            }
        }
        sum+=dist[pos];//加上权值
        vis[pos]=true;
        //更新权值
        for(j=1; j<=n; j++) {
            if(!vis[j] && dist[j]>map[pos][j]) {
                dist[j]=map[pos][j];
            }
        }
    }
    return sum;
}
int main() {
    int n;
    while(cin>>n) {
        init();
        //memset(map,MAX,sizeof(map));
        if(n==0) break;
        int i,j,a,b,d,state;
        for(i=0; i<n*(n-1)/2 ; i++) {
           // cin>>a>>b>>d;
            scanf("%d%d%d",&a,&b,&d);
            if(d<map[a][b]) {
                map[a][b]=map[b][a]=d;
            }
        }
        cout<<prim(n)<<endl;
    }
    return 0;
}

2、kruskal

1.简介

Kruskal算法是一种用来寻找最小生成树的算法，由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪婪算法的应用。和Boruvka算法不同的地方是，Kruskal算法在图中存在相同权值的边时也有效。

2.过程

1.首先将G的n个顶点看成n个孤立的连通分支（n个孤立点）并将所有的边按权从小大排序。

2.按照边权值递增顺序，如果加入边后存在圈则这条边不加，直到形成连通图（到n-1条边）

3.证明

对图的顶点数n做归纳，证明Kruskal算法对任意n阶图适用。

归纳基础：

n=1，显然能够找到最小生成树。

归纳过程：

假设Kruskal算法对n≤k阶图适用，那么，在k+1阶图G中，我们把最短边的两个端点a和b做一个合并操作，即把u与v合为一个点v’，把原来接在u和v的边都接到v’上去，这样就能够得到一个k阶图G'(u,v的合并是k+1少一条边)，G’最小生成树T’可以用Kruskal算法得到。

我们证明T’+{<u,v>}是G的最小生成树。

用反证法，如果T’+{<u,v>}不是最小生成树，最小生成树是T，即W(T)<W(T’+{<u,v>})。显然T应该包含<u,v>，否则，可以用<u,v>加入到T中，形成一个环，删除环上原有的任意一条边，形成一棵更小权值的生成树。而T-{<u,v>}，是G’的生成树。所以W(T-{<u,v>})<=W(T’)，也就是W(T)<=W(T’)+W(<u,v>)=W(T’+{<u,v>})，产生了矛盾。于是假设不成立，T’+{<u,v>}是G的最小生成树，Kruskal算法对k+1阶图也适用。

由数学归纳法，Kruskal算法得证。

4.图像演示

图例描述：

首先第一步，我们有一张图Graph，有若干点和边

将所有的边的长度排序，用排序的结果作为我们选择边的依据。这里再次体现了贪心算法的思想。资源排序，对局部最优的资源进行选择，排序完成后，我们率先选择了边AD。这样我们的图就变成了右图

在剩下的变中寻找。我们找到了CE。这里边的权重也是5

依次类推我们找到了6,7,7，即DF，AB，BE。

下面继续选择， BC或者EF尽管现在长度为8的边是最小的未选择的边。但是现在他们已经连通了（对于BC可以通过CE,EB来连接，类似的EF可以通过EB,BA,AD,DF来接连）。所以不需要选择他们。类似的BD也已经连通了（这里上图的连通线用红色表示了）。

其中A保存最小生成树，MAKE-SET(v)表示构造一棵只有顶点v的树，
FIND-SET(u)表示找u所在树的根节点，Union(u, v)表示合并u和v的所在树：
　　　　MST-KRUSKAL(G, W)
　　　　　　A←∅
　　　　　　for each vertex v∈V[G]
　　　　　　　　do MAKE-SET(v)
　　　　　　sort the eages of E into nondecreasing order by weight w
　　　　　　for each eage(u, v)∈E, teken in nondecreasing order by weight
　　　　　　　　do if(FIND-SET(u) ≠ FIND-SET(v))
　　　　　　　　　　then A←A∪{ (u, v) }
　　　　　　　　　　　　Union(u, v)
　　　　return A

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

#define maxn 110    //最多点个数
int n, m;   //点个数，边数
int parent[maxn];   //父亲节点，当值为-1时表示根节点
int ans;    //存放最小生成树权值
struct eage     //边的结构体，u、v为两端点，w为边权值
{
    int u, v, w;
}EG[5010];

bool cmp(eage a, eage b)    //排序调用
{
    return a.w < b.w;
}

int Find(int x)     //寻找根节点，判断是否在同一棵树中的依据
{
    if(parent[x] == -1) return x;
    return Find(parent[x]);
}

void Kruskal()      //Kruskal算法，parent能够还原一棵生成树，或者森林
{
    memset(parent, -1, sizeof(parent));
    sort(EG+1, EG+m+1, cmp);    //按权值将边从小到大排序
    ans = 0;
    for(int i = 1; i <= m; i++)     //按权值从小到大选择边
    {
        int t1 = Find(EG[i].u), t2 = Find(EG[i].v);
        if(t1 != t2)    //若不在同一棵树种则选择该边，合并两棵树
        {
            ans += EG[i].w;
            parent[t1] = t2;
        }
    }
}
int main()
{
    while(~scanf("%d%d", &n,&m))
    {
        for(int i = 1; i <= m; i++)
            scanf("%d%d%d", &EG[i].u, &EG[i].v, &EG[i].w);
        Kruskal();
        printf("%d\n", ans);
    }
    return 0;
}

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

#define maxn 110    //最多点个数
int n, m;   //点个数，边数
int parent[maxn];   //父亲节点，当值为-1时表示根节点
int ans;    //存放最小生成树权值
struct eage     //边的结构体，u、v为两端点，w为边权值
{
    int u, v, w;
}EG[5010];

bool cmp(eage a, eage b)    //排序调用
{
    return a.w < b.w;
}

int Find(int x)     //寻找根节点，判断是否在同一棵树中的依据
{
    if(parent[x] == -1) return x;
    return Find(parent[x]);
}

void Kruskal()      //Kruskal算法，parent能够还原一棵生成树，或者森林
{
    memset(parent, -1, sizeof(parent));
    int cnt = n;        //初始时根节点数目为n个
    sort(EG+1, EG+m+1, cmp);    //按权值将边从小到大排序
    ans = 0;
    for(int i = 1; i <= m; i++)     //按权值从小到大选择边
    {
        if(cnt == 1) break;     //当根节点只有1个时，跳出循环
        int t1 = Find(EG[i].u), t2 = Find(EG[i].v);
        if(t1 != t2)    //若不在同一棵树种则选择该边，
        {
            ans += EG[i].w;
            parent[t1] = t2;
            cnt--;      //每次合并，减少一个根节点
        }
    }
}
int main()
{
    while(scanf("%d", &n), n)
    {
        m = n*(n-1)/2;  //完全图
        for(int i = 1; i <= m; i++)
            scanf("%d%d%d", &EG[i].u, &EG[i].v, &EG[i].w);
        Kruskal();
        printf("%d\n", ans);
    }
    return 0;
}