2013年(118)
分类: C/C++
2013-10-18 15:41:48
原文地址:数据结构深入剖析(14)--最小连通图 作者:mq24705
一、 最小连通网
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 +{(u,v)}
U = U + {v}
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算法是针对边展开的,适合于边的数量较少的情况。