生成树kruskal算法实现.docx

kruskal 算法的实现）
一。需求分析：
题目：最小生成树kruskal 算法的实现
问题描述：任意创建一个图，用 kruskal 算法求去他的最小生成树。
举例：若要在 n 个城市之间建设通信网络，只需要架设n-1 条线路即可;//先把矩阵中所有元素赋值为0
for ( i = 1; i <= G->arcnum; i++)// 输入边和权值
G->arc[n][m].adj = G->arc[m][n].adj = 1;// 将输入的顶点记录为1
getchar();
printf(" 请输入 %d 与 %d 之间的权值 :\n", n, m);
printf(" 邻接矩阵为 :\n"); 输出邻接矩阵
以上是图的创建，邻接矩阵的建立将辅助权值排序
void MiniSpanTree(MGraph *G)// 生成最小生成树
{
}
sort(edges, G);//sort 函数调用，对权值进行排序
void sort(edge edges[],MGraph *G)// 对权值进行排序
void Swapn(edge *edges,int i, int j)// 交换权值 以及头和尾
在对权值排序时，若 (edges[i].weight > edges[j].weigh) 调用函数 swapn 交换这两条
边的权值以及头和尾顶点 以上是对权值进行排序，排序之后将有利于回路的判断，从而求出最小生成树
printf(" 最小生成树为 :\n");
for (i = 1; i <= G->arcnum; i++)// 核心部分
{
n = Find(parent, edges[i].begin);
m = Find(parent, edges[i].end);
if (n != m)// 判断是否有回路，如果有，舍弃
{
parent[m] = n;
printf("<< %d, %d >>%d\n", edges[i].begin, edges[i].end, edges[i].weight);
}
}
}
int Find(int *parent, int f)// 找尾
{
while ( parent[f] > 0)
{
f = parent[f];
}
return f;关键代码输出最小生成树
以下是主函数部门
int main(void)〃 主函数
{
MGraph *G;
G = (MGraph*)malloc(sizeof(MGraph));
if (G == NULL)
{
printf("memory allcation failed,goodbye");
exit(1);
}
CreatGraph(G);
MiniSpanTree(G);
system("pause");
return 0;
}
主函数通过调用不同的函数模块来实现的功能 以下是函数关系的调用图
Main()
CreatGraph()MiniSpanTree()
Sott ( )Find()
Swapn()
.调试分析
1由于对函数调用关系不是非常清楚，导致在程序设计的时候思路不是非常的清晰
2该程序只能满足图顶点比较少的最小生成树的实现，如果用户要求更大的空间，可以 在创建图的时候开辟更大的空间。
3在程序输入的时候，必须顶点数值小的先输入，否则程序将会出错。这也是程序应该 改进的地方。
4算法的时空分析
1,对矩阵的初始化，设输入一个 n个顶点的图，那个将要对矩阵的nxn个元素进行初
始化，所以时间复杂度为O(N2)
2,输入权值和边的时间复杂度为O(n),所以构建图的时间复杂度为O(N2+N)
(N2)。空间复杂度为 S (N2)
4在求最小生成树函数中，对边进行标记的时间复杂度为O(N2)。对权值进行排序的时
间复杂度为O(N2),对parent数组赋值的时间复杂度为o(n),所以该函数的时间复杂
度为 O ( 2N2+N )
5过这次课程设计，一方面我加深对课内所学的有关数据的逻辑结构和存储表示、数 据结构的选择和应用、算法的设计和时空分析等课程基本内容的理解，另一方面，使
我在序设计方法(如抽象数据类型、结构化分析、模块化设计和结构化设计)、C语
言程序调试和测试方面受到比较系统的严格的训练。
.用户使用说明
1,输入图的顶点数和变数
2任意输入两个图中连接的顶点
3输入这两个顶点的权值
具体步骤图如下
输入完数据之后，按enter键将会显示以下结果
最后按任意键退出，可以进行其他图最小生成树的实现