克鲁斯卡尔算法实验报告

实 验 报 告

实验原理：

Kruskal 算法是一种按照图中边的权值递增的顺序构造最小生成树的方法。其基本思想是：设无向连通网为G＝（V，E），令G 的最小生成树为T，其初态为T＝（V，{}），即开始时，最小生成树T 由图G 中的n 个顶点构成，顶点之间没有一条边，这样T 中各顶点各自构成一个连通分量。然后，按照边的权值由小到大的顺序，考察G 的边集E 中的各条边。若被考察的边的两个顶点属于T 的两个不同的连通分量，则将此边作为最小生成树的边加入到T 中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T 中的连通分量个数为1 时，此连通分量便为G 的一棵最小生成树。

如教材153页的图4.21(a)所示，按照Kruskal 方法构造最小生成树的过程如图4.21 所示。在构造过程中，按照网中边的权值由小到大的顺序，不断选取当前未被选取的边集中权值最小的边。依据生成树的概念，n 个结点的生成树，有n－1 条边，故反复上述过程，直到选取了n－1 条边为止，就构成了一棵最小生成树。

实验目的：

本实验通过实现最小生成树的算法，使学生理解图的数据结构存储表示，并能理解最小生成树Kruskal 算法。通过练习，加强对算法的理解，提高编程能力。

实验内容：

第1页

（1）假定每对顶点表示图的一条边，每条边对应一个权值；

（2）输入每条边的顶点和权值；

（3）输入每条边后，计算出最小生成树；

（4）打印最小生成树边的顶点及权值。

实验器材（设备、元器件）：

PC机一台，装有C语言集成开发环境。

数据结构与程序： #include #include #include using namespace std; #define X 105 typedef struct Edge

第2页

{ int w; int x, y; } Edge;

class GraphNode { public: int data; int father; int child;

} GraphNode[X]; 结点）

Edge edge[X*X];

//储存边的struct，并储存边两端的结点

//储存点信息的并查集类（点的值，父结点，子

第3页

bool comp(const Edge, const Edge); void update(int); int main() {

int node_num; int sum_weight = 0;

FILE *in = fopen(\"C:\\\\Users\\\\瑞奇\\\\Desktop\\\\编程实验\\\\数据结构实验\\\\FileTemp\\\\in.txt\

cout << \"Reading data from file...\" << endl << endl;

//cout << \"Please input the total amount of nodes in this Graph: \"; //cin >> node_num;

fscanf(in, \"%d\

//cout << \"Please input the data of each node: \" << endl;

第4页

for(int i = 1;i <= node_num;i++) {

//cin >> GraphNode[i].data;

fscanf(in, \"%d\GraphNode[i].father = GraphNode[i].child = i; }

//初始化点集

//cout << \"Please input the relation between nodes in this format and end with (0 0 0):\" << endl << \"(first_node second_node egde_weight)\" << endl; int x, y, w, tmp_cnt = 1;

//while(cin >> x >> y >> w && w)

while(fscanf(in, \"%d%d%d\

edge[tmp_cnt].w = w, edge[tmp_cnt].x = x, edge[tmp_cnt++].y = y;

第5页

fclose(in);

sort(edge+1, edge+tmp_cnt, comp);

//对边权进行排序

cout << \"The MinSpanTree contains following edges: \" << endl << endl;

for(int i = 1;i <= tmp_cnt;i++)

//循环找最小边

if(GraphNode[edge[i].x].father != GraphNode[edge[i].y].father) {

int n = edge[i].x; int m = n;

if(GraphNode[m].father != m) {

m = GraphNode[m].father;

GraphNode[m].father = GraphNode[edge[i].y].father;

第6页

//使用并查集对边是否可用进行判断

}

GraphNode[edge[i].x].father = GraphNode[edge[i].y].father; GraphNode[edge[i].y].child = GraphNode[edge[i].x].child; while(GraphNode[n].child != n) n = GraphNode[n].child; update(n);

//在合并点集后对并查集进行更新

//计算总权

sum_weight += edge[i].w;

cout << \"\\" << \"The edge between \" << GraphNode[edge[i].x].data << \" & \" << GraphNode[edge[i].y].data << \" with the weight \" << edge[i].w << endl; }

cout << endl << \"And the total weight of the MinSpanTree add up to: \" << sum_weight << endl; return 0;

第7页

}

bool comp(const Edge a, const Edge b) {

return a.w < b.w; }

void update(int n) {

if(GraphNode[n].father == n) return;

GraphNode[GraphNode[n].father].child = GraphNode[n].child; //更新孩子结点

update(GraphNode[n].father);

//递归更新

GraphNode[n].father = GraphNode[GraphNode[n].father].father;

第8页

//更新父结点 }

程序运行结果：

运行程序，程序读取文件，获取文件中关于图的信息：结点数，结点值，结点间边权。

然后使用Kruskal算法对录入信息进行处理：

1.对边权排序

2.取最小权边，若边的端结点不在同一集合众，则使边的端结点加入集合并删除

该边；若边的端结点本来就在同一集合中，直接删除该边

3.循环执行步骤2，直到集合中包含所有结点和结点数-1条边

输入为： 6

1 2 3 4 5 6

第9页

1 2 6 1 3 1 1 4 5 2 3 5 2 5 3 3 4 5 3 5 6 3 6 4 4 6 2 5 6 6

程序运行结果如下图：第10页

实验结论：

Kruskal算法其实是一种贪心算法，每次选取符合条件的边，加入边集（此程序中直接输出）。直到所有结点和最少边全部包含在同一集合中，算法结束。 总结及心得体会：

在使用并查集的时候，注意在合并集合后要更新并查集的父结点和子结点。

其实Kruskal算法的复杂度为O(E^2)，其复杂度和边条数有关，和结点数无关，所以适用于稀疏图。

第11页