数据结构深入剖析（14）--最小连通图

一、      最小连通网

1.    问题的提出

如何在图中选择n-1条边使得n个顶点间两两可达，且这n-1条边的权值之和最小？

2.    目标

      1）必须使用且仅使用该网络中的n-1条边来连接网络中的n个顶点。

      2）不能使用产生回路的边。

      3）各边上的权值的总和达到最小。

3.    Prim算法

基本思想：

从图N = { V, E }中选择某一顶点u0 进行标记，之后选择与它关联的具有最小权值的边(u0, v)，并将顶点v 进行标记。

 反复在一个顶点被标记，而另一个顶点未被标记的各条边中选择权值最小的边(u, v)，并将未标记的顶点进行标记。

如此继续下去，直到图中的所有顶点都被标记为止。

算法步骤：

a、         从某一顶点u0出发，使得U = {u0},TE = { }.

b、        每次选择一条边，这条边是所有（u，v）中权值最小的边，且u属于U，v属于V – U。修改U和TE：

TE = TE +｛（ｕ，ｖ）｝

Ｕ　＝　Ｕ　＋　｛ｖ｝

c、         当U != V时，转2；否则，结束。

4.    Prim算法实现

#include

#include

#define VNUM 9

#define MV 65536

 

int P[VNUM];

int Cost[VNUM];

int Mark[VNUM];

//二维矩阵保存图。

int Matrix[VNUM][VNUM] =

{

{0,10,MV,MV,MV,11,MV,MV,MV},

{10,0,18,MV,MV,MV,16,MV,12},

{MV,18,0,22,MV,MV,MV,MV,8},

{MV,MV,22,0,20,MV,24,16,21},

{MV,MV,MV,20,0,26,MV,7,MV},

{11,MV,MV,MV,26,0,17,MV,MV},

{MV,16,MV,24,MV,17,0,19,MV},

{MV,MV,MV,16,7,MV,19,0,MV},

{MV,12,8,21,MV,MV,MV,MV,0}

};

void Prim(int sv)

{

int i = 0;

int j = 0;

if((0 <= sv) && (sv < VNUM)){

      for(i = 0;i < VNUM;i++){

            Cost[i] = Matrix[sv][i];

            P[i] = sv;

            Mark[i] = 0;

      }

      Mark[sv] = 1;

      for(i = 0;i < VNUM;i++){

            int min = MV;

            int index = -1;

           

            for(j = 0; j < VNUM;j++){

                 if(!Mark[j] && (Cost[j] < min)){

                       min = Cost[j];

                       index = j;

                 }

            }

            if(index > -1){

                 Mark[index] = 1;

                 printf("(%d,%d,%d)\n",P[index],index,Cost[index]);

            }

            for(j = 0; j < VNUM;j++){

                 if(!Mark[j] && (Matrix[index][j] < Cost[j])){

                       Cost[j] = Matrix[index][j];

                       P[j] = index;

                 }

            }

      }

}

}

int main(int argc, char *argv[])

{

Prim(0);

return 0;

}

5.    Kruskal算法

1）         基本思想

a、         对于n个顶点的图G = {V,E}

b、        构造一个只有n个顶点，没有边的图T = {V，空集}

c、         在E中选择一条具有最小权值的边，若该边的两个顶点不构成回路，则将此边加入到T中；否则将此边舍去，重新选择一条权值最小的边。

d、         如此重复下去，直到所有顶点都连通为止。

2）         算法实现

a、         定义边结构体

typedef struct _tag_Edge

{

    int begin;

    int end;

    int weight;

}TEdge;

b、        定义边集数组并排序

c、         定义辅助数组p[n]，其中n为顶点数目

p[n]用于记录边顶点的首尾连接关系

例如：

3）         算法核心思想

遍历edges数组中的每个元素

a、         通过P数组查找begin顶点的最终连接点v1

b、        通过P数组查找end顶点的最终连接点v2

if(v1 != v2)则当前边为最小连通网中的边，记录连接关系P[v1] = v2

else if(v1 == v2)则产生回路，舍弃当前边。

6.    算法实现

7.    小结

Prim算法是针对顶点展开的，适合于边数较多的情况。

Kruskal算法是针对边展开的，适合于边的数量较少的情况。