数据结构小组作业二 最小代价生成树的三种算法

 

 

该无向图的邻接矩阵为

0 2 0 0 0 1
2 0 3 0 2 0
0 3 0 1 0 0 
0 0 1 0 3 0
0 2 0 3 0 2
1 0 0 0 2 0

下面将会以该无向图为例介绍最小代价生成树的三种算法：①prim算法 ②kruskal算法 ③去边法。

 

Prim算法

1.a将图中顶点分为两个集合，其中集合X包含图的一个顶点，集合Y包含除了外的所有其它顶点

2.将跨接在这两个集合的权值最小的边加入图中，并将其依附在集合Y中的顶点从Y中移到集合X中

3.反复过程2，直到集合Y为空，所得生成子图即为最小生成树

算法描述很简单，但是在编写程序的时候，难以实现的是寻找跨接X、Y两个集合的边。于是引入以下的结构

顶点（数组下标）i	A(0)	B(1)	C(2)	D(3)	E(4)	F(5)
weight
flag
sign

typedef struct {
	int weight;
	int flag;
	int sign;
}primtable;

 **说明：flag用来表示该结点是否被加入到集合X中；sign&weight表示，连接 i 和sign的边的权值为weight

首先，顶点A作为起始点是一定会被选中的。然后每次对于primtable中flag为1的点，寻找它们的邻接且未在X中的点，选择边权值最小的点加入X中。重复该步骤直至primtable中的flag全为1。 

最后得到的primtable：

顶点（数组下标）i	A(0)	B(1)	C(2)	D(3)	E(4)	F(5)
weight	0	2	3	1	2	1
flag	1	1	1	1	1	1
sign		A	B	D	F	A

输出边的信息：

---

Kruskal算法

1.将图中所有边按权值从小到大排序

2.取权值最小的边，加入图中，判断是否形成了回路，若无，则保留此边。否则去掉此边，重取权值较小的边

3.重复过程2直到全部顶点均连通为止

Kruskal算法编程实现的难点在于，如何判断新加进来的边是否与之前的边构成回路。这里引入并查集。

1.首先先把所有的边按权值大小排序，什么算法都可以

//存储边的数据结构
typedef struct{
	int a;
	int b;//a、b分别代表两个顶点 
	int weight;
}arc;

2.定义数组v[x]，即为并查集。初始化并查集，令v[i] = i .

3.此处引入一个寻根函数。对于结点x，若v[x] != x，则令x = v[x]，一直循环直至 x' = v[x']，此处的x' or v[x'] 即为x的根。

int findroot(int v[],int x)
{
	while(v[x] != x)
	{
		x = v[x];
	}
	
	return x;
}

4.对于排好序的所有的边（从小到大），依次判断加入后是否形成回路。即加入的边的两个结点的根是否相同。相同则形成回路，去掉该边；不相同则保留该边，并更新 v[a] = b

 

 

---

去边法

1.将图中所有边权值从大到小排序

2.去掉权值最大的边，若图不再连通则保留此边，在选取下一权值较大的边去掉

3.反复此过程，直至图中只剩下n-1条边为止 

这个算法描述也很简单，手工也不难实现。编程实现的难点在于，如何判断一个图是否连通？ 

判断图连通的方法有很多，这里采取的是如下方法：

开始时各个顶点均各为一个连通分量，根据顶点之间的邻接关系，逐个合并。若最后只有一个连通分量，则该图为一连通图。

这里还是采用并查集实现以上功能。

1.初始化并查集，v[x] = x

2.循环遍历所有在图中的边，将v[b]赋值为a

typedef struct{
	int a;
	int b;//a、b分别代表两个顶点 
	int weight;
}arc;

3.用寻根函数findroot操作所有结点，更新结点的根。

4.若最后得到的并查集中，所有结点的根是相同的，则说明各点连通，该图为连通图。