您的位置: 网站首页 > 程序开发 > 数据结构 > 第6章 图 > 【6.4 最小生成树】

6.4 最小生成树

 

6.4  最小生成树

6-9  完全图A示意图

 

最小生成树是以最少的边数来连接图中所有的顶点。如   6-9中有一个完全图A

6-10中的树是其部分的最小生成树。

6.3节提到了图的遍历,可用于画出图的最小生成树。假如使用深度优先搜索的遍历方式,则称为深度优先搜索最小生成树。若使用广度优先搜索的遍历方式,则称为广度优先搜索最小生成树。

6-10  完全图A的部分最小生成树示意图

G=(V, E)是一个图,而S = (V, T)G的最小生成树。其中T是遍历时所访问过的边,以K表示遍历后未被访问的边。此时最小生成树具有下列几点特性:

·    E=T+K

·    V中的任何两个顶点V1V2S中有唯一的边。

·    K中任何一个边插入于S中,会形成回路。

若图中每一个边加上一些数值,此数值称为权(Weight),而称此图为权图(Weight Graph)。假设此权是代价(Cost)或距离(Distance),则称此图为网(Network)。从最小生成树的定义可知一个图有许多不同的最小生成树,假如在网中有一个最小生成树具有最小代价,则求最小代价最小生成树有两种方法:普里姆算法(Prim’s algorithm)和克鲁斯卡尔算法(Kruskal’s algorithm)。

6.4.1  普里姆算法

有一个网G=(V,E),其中V={1,2,3,,n },起初设置U{1}UV是两个顶点的集合,然后从V-U集合中找一个顶点x,能与U集合中的某顶点形成最小的边,把这一个顶点x插入U集合,继续此步骤,直到U集合等于V集合为止。

假如有一个网A,如图6-11所示。

若以普里姆算法来找最少代价的最小生成树,其过程如下:

1V={1,2,3,4,5,6,7}U={1}

2)从V-U={2,3,4,5,6,7}中找一顶点,与U={1}顶点能形成最小代价的边是顶点6,然后将此顶点加到U中,U={1,6},如图6-12所示。

3)此时V-U={2,3,4,5,7},从这些顶点找一个顶点,与U={1,6}顶点能形成最小代价的边,答案是顶点5,因为其代价或距离为9;将此顶点加到U中,U={1,5,6}V-U={2,3,4,7},如图6-13所示。

6-11  A示意图

                           

6-12  执行步骤(2)后的最小生成树示意图      6-13  执行步骤(3)后的最小生成树示意图

4)以同样的方法找到一个顶点2,能与V中的顶点1形成最小的边,将此顶点加到U中,U={1,2,5,6}V-U={3,4,7},如图6-14所示。

5)同样方法将顶点3插入U中,U={1,2,3,5,6}V-U={4,7},如图6-15所示。

                

6-14  执行步骤(4)后的最小生成树示意图          6-15  执行步骤(5)后的最小生成树示意图

6)以同样的方法将顶点4插入U中,U={1,2,3,4,5,6}V-U={7},如图6-16所示。

7)将顶点7插入U中,U={1,2,3,4,5,6,7}V-U=?V=U,此时的图就是最小代价最小生成树,如图6-17所示。

             

6-16  执行步骤(6)后的最小生成树示意图         6-17  执行步骤(7)后的最小生成树示意图

6.4.2  克鲁斯卡尔算法

有一个网G=(V,E)V=P{1,2,3,,n}E中每一边都有一个代价,T=(v, )表示开始时T没有边。首先从E中找具有最小代价的边;若此边插入T中不形成回路,则将此边从E删除并插入T中,直到T中含有n-1个边为止。

以克鲁斯卡尔算法来找出最小代价生成树,其过程如下:

1)在图6-11中顶点1到顶点6的边具有最小代价,如图6-18所示。

2)同样方法顶点2到顶点3的边具有最小代价,如图6-19所示。

                   

6-18  执行完第(1)步后的最小生成树示意图       6-19  执行完第(2)步后的最小生成树示意图

3)以同样的方法可知顶点2到顶点4的边有最小代价,如图6-20所示。

4)以同样的方法可知顶点5到顶点6的边有最小代价,如图6-21所示。

            

6-20  执行完第(3)步后的最小生成树示意图     6-21  执行完第(4)步后的最小生成树示意图

5)从其余的边中,顶点3到顶点4具有最小代价,但此边插入T后会形成回路,故不考虑,而把顶点2到顶点7的边插入T中,如图6-22所示。

6)由于顶点4到顶点7的边会使T形成循环,故不考虑,最后最小代价生成树如图6-23所示。

不论由普里姆算法或克鲁斯卡尔算法来求最小代价最小生成树,所得到的图是一样的。

           

6-22  执行完第(5)步后的最小生成树示意图    6-23  执行完第(6)步后的最小生成树示意图

使用克鲁斯卡尔算法求最小生成树的程序如下:

/*file name: kruskal.c*/

/*使用kruskal's 算法求最小生成树*/

 

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

 

#define MAX_V 100       /*最大节点数*/

#define TRUE 1

#define FALSE 0

 

typedef struct

{

    int vertex1;

    int vertex2;

    int weight;

    int edge_deleted;

} Edge;

 

typedef struct

{

    int vertex[MAX_V];

    int edges;

} Graph;

 

Edge E[MAX_V];

Graph T;

 

int total_vertex;

int total_edge;

int adjmatrix[MAX_V][MAX_V];  /*store matrix weight*/

 

void kruskal();

void addEdge(Edge);

void build_adjmatrix();

Edge mincostEdge();

int cyclicT(Edge e);

void showEdge();

void main()

{

    Edge e;

    int i,j,weight;

 

    build_adjmatrix();

 

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

        for(j=i+1;j<=total_vertex;j++)

        {

            weight=adjmatrix[i][j];

            if(weight!=0)

            {

                e.vertex1=i;

                e.vertex2=j;

                e.weight=weight;

                e.edge_deleted=FALSE;

                addEdge(e);

            }

        }

 

    showEdge();

    /*init T*/

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

        T.vertex[i]=0;

    T.edges=0;

 

    puts("\nMinimum cost spanning tree using Kruskal");

    puts("-------------------------------------------");

    kruskal();

}

 

void build_adjmatrix()

{

    FILE *fptr;

    int vi,vj;

 

    fptr=fopen("kruskal.dat","r");

    if(fptr==NULL)

    {

        perror("kruskal.dat");

        exit(0);

    }

 

    /*读取节点总数*/

    fscanf(fptr,"%d",&total_vertex);

 

    for(vi=1;vi<=total_vertex;vi++)

        for(vj=1;vj<=total_vertex;vj++)

            fscanf(fptr,"%d",&adjmatrix[vi][vj]);

 

    fclose(fptr);

}

 

void addEdge(Edge e)

{

    E[++total_edge]=e;

}

 

void showEdge()

{

    int  i=1;

 

    printf("total vertex=%d",total_vertex);

    printf("total_edge=%d\n",total_edge);

    while(i<=total_edge)

    {

        printf("V%d  <----->  V%d   weight= %d\n",E[i].vertex1,

                E[i].vertex2,E[i].weight);

        i++;

    }

}

 

Edge mincostEdge()

{

    int i,min;

    long minweight=10000000;

 

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

    {

        if(!E[i].edge_deleted && E[i].weight<minweight)

        {

            minweight=E[i].weight;

            min=i;

        }

    }

    E[min].edge_deleted=TRUE;

    return E[min];

}

 

 

void kruskal()

{

    Edge e;

    int loop=1;

    while(T.edges!=total_vertex-1)

    {

        e=mincostEdge();

 

        if(!cyclicT(e) )

        {

        printf("%dth min edge : ",loop++);

         printf("V%d  <----->  V%d  weight=%d\n",e.vertex1,e.vertex2,e.weight);

        }

    }

}

 

int cyclicT(Edge e)

{

    int v1=e.vertex1;

    int v2=e.vertex2;

 

    T.vertex[v1]++;

    T.vertex[v2]++;

    T.edges++;

 

    if(T.vertex[v1]>=2 && T.vertex[v2]>=2)

    {

        if(v2==2)

            return FALSE;

        T.vertex[v1]--;

        T.vertex[v2]--;

        T.edges--;

        return TRUE;

    }

    else

        return FALSE;

}