kruskal算法求最小生成树.docx

数据结构课程设计
Kruskal算法求最小生成树
学院： 班级： 学号； 姓名； 指导老师; 完成日期:
目录
（一） 需求分析・
（二） 概要设计・
（三）详细设计・
（四）主函数设计•
（五）经验体会・
（六）源代jvGvexnum;j++)
{
if(Garcs[i][j]vINF)
{
E[k].u=i;
E[k].v=j;
E[k].w=Garcs[i][j];
k++;
}
}
} for(i=1;i<k;i++) //按权值递增进行直接插入排序
{
temp = E[i];
j = i-1; 〃从右向左在有序区E【0, i-1】中找E【i】的
插入位置
while(j>=0 && <E[j].w)
{
E[j+1] = E[j]; 〃将权值大于E【i】.w的记录后移
j--；
}
E[j+1] = temp; 〃在j+1处插入E【i】
}
} int Locate(MGraph Gchar* a)//图G中存在和a相同的顶点，返回该顶点在图中的 位置
{
int i;
for(i=0; ivGvexnum; i++) {
if(strcmp(Gvexs[i],a)==O)
return i;
}
return 0;
}
4、 主函数设计
int main()
{
Edge E[MAXE];
MGraph G;
Create(G);
SortEdge(GE); printf("\n");
Kruskal(E,Gvexnum,);
return 0;
}
5、 经验体会
做最小生成树期间遇到了很多困难，但是得到了同学的很多帮助，所以，最 终还是得出了结果，下面就谈一谈我对用kruskal算法求最小生成树的经验和教 训。
在创造无向图时，首先要了解究竟是怎样将自己所输入的图能够用邻接矩阵的方 法表示出来；其次是要了解kruskal的具体用法，由课本上没有现成的方法，所 以，只能看一些完整的关于该算法的代码。而这段代码的主要意图是将六个顶点 当做六个孤立的森林。由于在前面的SortEdge函数当中已经将图中各边及其权 值分别按从小到大顺序排列，所以在后面的算法中，当两个顶点不在一棵树 内，即像代码中所写：if(s n1!=s n2)，那么就可将这条新的边加入到这棵树 中间来，否则，就进行下一条边。这也就是在测试用例当中，为什么权值相同 的两条边v1 v4 5 v2 v3 5中，要选择后者加入到最小生成树中，因为如果是前
面的那条边，就会和前面所生成的树中形成回路(由于已经有了 v1和v4)。这 样就生成了最小生成树。
虽然知道了很多东西，可是任然很多东西需要自己好好学习，这一学期学的并 不好，希望自己在接下来的时间可以把更多的时间放在编程上，以求能达到更 好的能力，不至于在很多方面都需要寻求他人的帮助。自己将来一定可以做到 最好！
6、源代码及调试分析
#include <>
#include <string・h>
#define INF 10000
#define MAX 10
#define MAXE 100
typedef struct
{
int u;
//边的起始顶点
int v;
//边的终止顶点
int w;
//边的权值
}Edge;
//储存图的顶点
typedef struct
{
char vexs[10][MAX];
//存储顶点
int arcs[MAX][MAX];
//存储边
int vexnum,arcnum;
//定义顶点和边
}MGraph;
int Locate(MGraph G,char* a)〃图G中存在和a相同的顶点，返回该顶点在 图中的位置
int i;
for(i=0; i<; i++)
{
if(s trcmp(G .v exs[i],a)==0) return i;
}
return 0;
}
void Create(MGraph &G) //采用数组(邻接矩阵)表示法,
构造无向图Go
{
int i,j,k,w;
char v1[10],v2[10];
scanf("%d%d",&,&); // 输入定点数和边数
for(i=0; i<G ・v exnum; i++)
scanf("%s", [i]);
for(i=0; i<; i++) // 初始化邻接矩阵
{
for(j=0; j<G ・v exnum; j++)
[i][j]