6.4 最小生成树
6.4 最小生成树
|
图6-9 完全图A示意图
|
图6-10中的树是其部分的最小生成树。
6.3节提到了图的遍历，可用于画出图的最小生成树。假如使用深度优先搜索的遍历方式，则称为深度优先搜索最小生成树。若使用广度优先搜索的遍历方式，则称为广度优先搜索最小生成树。
图6-10 完全图A的部分最小生成树示意图
若G=(V, E)是一个图，而S = (V, T)是G的最小生成树。其中T是遍历时所访问过的边，以K表示遍历后未被访问的边。此时最小生成树具有下列几点特性：
· E=T+K。
· V中的任何两个顶点V1及V2在S中有唯一的边。
· 将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}，U及V是两个顶点的集合，然后从V-U集合中找一个顶点x，能与U集合中的某顶点形成最小的边，把这一个顶点x插入U集合，继续此步骤，直到U集合等于V集合为止。
假如有一个网A，如图6-11所示。
若以普里姆算法来找最少代价的最小生成树，其过程如下：
（1）V={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;
}