图->连通性->最小生成树(普里姆算法)

文字描述

　　用连通网来表示n个城市及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价。对于n个定点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，我们要选择这样一个生成树，使总的耗费最少。这个问题就是构造连通网的最小代价生成树(Minimum Cost Spanning Tree: 最小生成树)的问题。一棵生成树的代价就是树上各边的代价之和。

　　有多种算法可以构造最小生成树，其他多数都利用的最小生成的MST(minimum spanning tree)性质: 假设N={V, {E}}是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值(代价)的边，其中u属于U， v属于V-U，则必存在一棵包含边(u,v)的最小生成树。该性质可以用反证法证明。

现介绍普里姆(Prim)算法是如何利用MST性质求连通图的最小生成树的：

假设N={V,{E}}是连通网，TE是N上最小生成树中边的集合。算法从U={u0} (u0属于V， TE={})开始，重复执行下述操作：在所有u属于U， v属于V-U 的边(u,v)属于E 中找一条代价最小的边(u0,v0)并入集合TE，同时v0并入U，直至U=V为止。

为实现这个算法需附设一个辅助数组closeedge, 以记录从U到V-U具有最小代价的边。对每个属于V-U的顶点vi ，在辅助数组中存在一个相应分量closedge[i-1],它包括两个域：

　　1：lowcose：存储该边上的权；显然closedge[i-1].lowcost = Min{cost(u,vi) | u属于U}

　　2：vex: 存储该边依附的U中的顶点。

示意图

算法分析

　　在代码实现中的MinSpanTree_PRIM函数中。若网中有n个顶点，则第一个初始化的循环语句的频度为n，第二个循环语句的频度为n-1；其中第二个循环中有两个内循环：其一是在 closedge[v].lowcost中求最小值，其频度为n-1；其二是重新选择具有最小代价的边，其频度为n。由此，普里姆算法的时间复杂度为n^2, 与网中的边数无关，因此使用适用于求边稠密的网的最小生成树。

代码实现

 #include <stdio.h>

 #include <stdlib.h>

 #include <string.h>

 #define DEBUG

 #ifdef DEBUG

 #include <stdarg.h>

 #define LOG(args...) _log_(__FILE__, __FUNCTION__, __LINE__, ##args);

 void _log_(const char *file, const char *function, int line, const char * format, ...)

 {

     char buf[] = {};

     va_list list;

     va_start(list, format);

     sprintf(buf, "[%s,%s,%d]", file, function, line);

     vsprintf(buf+strlen(buf), format, list);

     sprintf(buf+strlen(buf), "\n");

     va_end(list);

     printf(buf);

 }

 #else

 #define LOG

 #endif // DEBUG

 #define INFINITY        100000    //最大值

 #define MAX_VERTEX_NUM    20        //最大顶点数

 //---------邻接矩阵的存储结构-----------------------------------------

 //////////////////////////////////////////////////////////////

 // 邻接矩阵作为图的存储结构

 //////////////////////////////////////////////////////////////

 typedef enum {DG, DN, UDG, UDN} GraphKind; //{有向图，有向网，无向图，无向网}

 typedef int  VRType;

 typedef char VertexType;    //顶点类型

 typedef struct{

     char note[];

 }InfoType;

 typedef struct ArcCell{

     VRType adj;        //顶点关系类型：1)对无权图，用1或0表示相邻否；2)对带权图，则为权值类型

     InfoType *info;    //该弧相关信息的指针

 }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

 typedef struct{

     VertexType vexs[MAX_VERTEX_NUM];    //顶点向量

     AdjMatrix arcs;        //邻接矩阵

     int vexnum, arcnum;    //图的当前顶点数和弧数

     GraphKind kind;        //图的种类标志

 }MGraph;

 //---------采用邻接矩阵创建无向网-----------------------------------------

 //////////////////////////////////////////////////////////////

 // 若G中存在顶点u，则返回该顶点在图中位置；否则返回-1。

 //////////////////////////////////////////////////////////////

 int LocateVex(MGraph G, VertexType v){

     int i = ;

     for(i=; i<G.vexnum; i++){

         if(G.vexs[i] == v){

             return i;

         }

     }

     return -;

 }

 //////////////////////////////////////////////////////////////

 // 采用数组表示法(邻接矩阵)，构造无向网

 //////////////////////////////////////////////////////////////

 int CreateUDN(MGraph *G)

 {

     printf("\n创建一个无向网(带权):\n");

     int i = , j = , k = , IncInfo = ;

     int v1 = , v2 = , w = ;

     char tmp[] = {};

     printf("输入顶点数，弧数，其他信息标志位: ");

     scanf("%d,%d,%d", &G->vexnum, &G->arcnum, &IncInfo);

     for(i=; i<G->vexnum; i++)

     {

         printf("输入第%d个顶点: ", i+);

         memset(tmp, , sizeof(tmp));

         scanf("%s", tmp);

         G->vexs[i] = tmp[];

     }

     for(i=; i<G->vexnum; i++)

     {

         for(j=; j<G->vexnum; j++)

         {

             G->arcs[i][j].adj = INFINITY;

             G->arcs[i][j].info = NULL;

         }

     }

     for(k=; k<G->arcnum; k++)

     {

         printf("输入第%d条弧: 弧尾, 弧头，权值: ", k+);

         memset(tmp, , sizeof(tmp));

         scanf("%s", tmp);

         sscanf(tmp, "%c,%c,%d", &v1, &v2, &w);

         i = LocateVex(*G, v1);

         j = LocateVex(*G, v2);

         G->arcs[i][j].adj = w;

         if(IncInfo){

             //

         }

         G->arcs[j][i] = G->arcs[i][j];

     }

     return ;

 }

 int CreateGraph(MGraph *G)

 {

     printf("输入图类型: -有向图(0), -有向网(1), -无向图(2), +无向网(3): ");

     scanf("%d", &G->kind);

     switch(G->kind)

     {

         case DG:

         case DN:

         case UDG:

             printf("还不支持!\n");

             return -;

         case UDN:

             return CreateUDN(G);

         default:

             return -;

     }

 }

 //////////////////////////////////////////////////////////////

 // 打印邻接矩阵中的信息

 //////////////////////////////////////////////////////////////

 void printG(MGraph G)

 {

     printf("\n打印邻接矩阵:\n");

     if(G.kind == DG){

         printf("类型：有向图；顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);

     }else if(G.kind == DN){

         printf("类型：有向网；顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);

     }else if(G.kind == UDG){

         printf("类型：无向图；顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);

     }else if(G.kind == UDN){

         printf("类型：无向网；顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);

     }

     int i = , j = ;

     printf("\t");

     for(i=; i<G.vexnum; i++)

         printf("%c\t", G.vexs[i]);

     printf("\n");

     for(i=; i<G.vexnum; i++){

         printf("%c\t", G.vexs[i]);

         for(j=; j<G.vexnum; j++){

             if(G.arcs[i][j].adj == INFINITY){

                 printf("INF\t");

             }else{

                 printf("%d\t", G.arcs[i][j].adj);

             }

         }

         printf("\n");

     }

 }

 //---------求最小生成树的算法。(普里姆算法)-----------------------------------------

 //////////////////////////////////////////////////////////////

 // 定义辅助数组CloseEdge： 记录从顶点集U到V-U的代价最小的边的辅助数组。

 //////////////////////////////////////////////////////////////

 struct Edge{

     VertexType adjvex;

     VRType  lowcost;

 }CloseEdge[MAX_VERTEX_NUM];

 //////////////////////////////////////////////////////////////

 // 返回辅助数组中， 权值最小的顶点的位置。

 //////////////////////////////////////////////////////////////

 int minimum(struct Edge edgelist[], int count)

 {

     int ret = -;

     int min = INFINITY;

     int i = ;

     for(i=; i<count; i++) {

         if ((edgelist[i].lowcost) && (edgelist[i].lowcost < min)) {

             ret = i;

             min = edgelist[i].lowcost;

         }

     }

     return ret;

 }

 //////////////////////////////////////////////////////////////

 // 采用普里姆算法求最小生成树的算法。

 //////////////////////////////////////////////////////////////

 void MinSpanTree_PRIM(MGraph G, VertexType v)

 {

     printf("\n采用普里姆算法求邻接矩阵存储的带权的无向网的最小生成树,所求最小生成树的边依次为:\n");

     int k = -;

     int i = ;

     int j = ;

     k = LocateVex(G, v);

     //辅助数组初始化

     for(j=; j<G.vexnum; j++){

         if(j!=k)

         {

             CloseEdge[j].adjvex = v;

             CloseEdge[j].lowcost = G.arcs[k][j].adj;

         }

     }

     //初始状态下， U={v}

     CloseEdge[k].lowcost = ;

     //选择其余的G.vexnum-1个顶点

     for(i=; i<G.vexnum; i++)

     {

         //求出T的下一个结点，第k个顶点

         k = minimum(CloseEdge, G.vexnum);

         //输出生成树的边

         printf("%c, %c\n", CloseEdge[k].adjvex, G.vexs[k]);

         //第k个顶点并入U集合

         CloseEdge[k].lowcost = ;

         //新顶点并入U后重新选择最小边。

         for(j=; j<G.vexnum; j++){

             if(G.arcs[k][j].adj < CloseEdge[j].lowcost){

                 CloseEdge[j].adjvex = G.vexs[k];

                 CloseEdge[j].lowcost = G.arcs[k][j].adj;

             }

         }

     }

 }

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

 {

     MGraph G;

     if(CreateGraph(&G) > -)

         printG(G);

     MinSpanTree_PRIM(G, G.vexs[]);

     return ;

 }

最小生成树(普里姆算法)

代码运行

/home/lady/CLionProjects/untitled/cmake-build-debug/untitled

输入图类型: -有向图(0), -有向网(1), -无向图(2), +无向网(3): 3

创建一个无向网(带权):

输入顶点数，弧数，其他信息标志位: 6,10,0

输入第1个顶点: a

输入第2个顶点: b

输入第3个顶点: c

输入第4个顶点: d

输入第5个顶点: e

输入第6个顶点: f

输入第1条弧: 弧尾, 弧头，权值: c,a,1

输入第2条弧: 弧尾, 弧头，权值: c,b,5

输入第3条弧: 弧尾, 弧头，权值: c,d,5

输入第4条弧: 弧尾, 弧头，权值: c,e,6

输入第5条弧: 弧尾, 弧头，权值: c,f,4

输入第6条弧: 弧尾, 弧头，权值: a,b,6

输入第7条弧: 弧尾, 弧头，权值: b,e,3

输入第8条弧: 弧尾, 弧头，权值: e,f,6

输入第9条弧: 弧尾, 弧头，权值: f,d,2

输入第10条弧: 弧尾, 弧头，权值: d,a,5

打印邻接矩阵:

类型：无向网；顶点数 6, 弧数 10

    a    b    c    d    e    f

a    INF    6    1    5    INF    INF

b    6    INF    5    INF    3    INF

c    1    5    INF    5    6    4

d    5    INF    5    INF    INF    2

e    INF    3    6    INF    INF    6

f    INF    INF    4    2    6    INF    

采用普里姆算法求邻接矩阵存储的带权的无向网的最小生成树,所求最小生成树的边依次为:

a, c

c, f

f, d

c, b

b, e

Process finished with exit code 0

巴特西

图->连通性->最小生成树(普里姆算法)

最新文章

热门文章