最小生成树的Kruskal算法实验报告.doc

大连民族学院 计算机科学与工程学院实验报告 实验题目： 最小生成树的Kruskal算法 课程名称： 离散数学 实验类型：□演示性 □验证性 □操作性 ■设计性 □综合性 专业：软件工程 班级：111 学生姓名：xx 学号：xx 实验日期：2012年12月6-28日 实验地点：金石滩校区机房201 实验学时： 10学时 实验成绩： 指导教师： 焉德军 姜楠 2012年 12月28 日 [实验原理] 设所给定无向连通加权图具有n个结点，m条边，首先，将各条边的权按从小到大的顺序排序。然后依次将这些边按所给图的结构放到生成树中去。如果在放置某一条边时，使得生成树形成回路，则删除这条边。这样，直至生成树具有n-1条边时，我们所得到的就是一棵最小生成树。 [实验内容] 给定无向连通加权图，编程设计求出其一棵最小生成树。 [实验目的] 通过算法设计并编程实现求出给定无向连通加权图的一棵最小生成树，加深学生对求最小生成树的Kruskal算法的理解。 [实验步骤] 边依小到大顺序得l1，l2，…，lm。 置初值：S，0i，1j。 若i=n-1，则转（6）。 若生成树边集S并入一条新的边lj之后产生的回路，则j+1j，并转（4）。 否则，i+1i；ljS（i）；j+1j，转（3）。 输出最小生成树S。 结束。 具体程序的C++实现如下： #include iostream using namespace std; const int MaxVertex = 20; const int MaxEdge = 100; const int MaxSize = 100; struct EdgeType { int from; int to; int weight; }; struct EdgeGraph { char vertex[MaxVertex]; EdgeType edge[MaxEdge]; int vertexNum; int edgeNum; }; int FindRoot(int parent[], int v); void InputInfo(); void Kruskal(EdgeGraph G) { int vex1,vex2,f,t; int i,num; int parent[MaxVertex]; for(i=0; iG.vertexNum; i++) { parent[i] = -1; } for(num =0,i=0; iG.edgeNum; i++) { vex1 = FindRoot(parent, G.edge[i].from); vex2 = FindRoot(parent, G.edge[i].to); if(vex1 != vex2) { cout ( G.edge[i].from , G.edge[i].to ) endl; f = G.edge[i].from; t = G.edge[i].to; cout ( G.vertex[f] , G.vertex[t] ) Weight: G.edge[i].weight endl; cout endl; parent[vex2] = vex1; num++; if(num == G.vertexNum-1) return; } } return; } int FindRoot(int parent[], int v) { int t; t = v; if(parent[t] -1) { t = parent[t]; } return t; } void InputInfo() { EdgeGraph G; cout Please input vertexNum , edgeNum: endl; cin G.vertexNum G.edgeNum; cout Please input the information of edges: endl; for(int i=0; iG.vertexNum; i++) { cin G.vertex[i]; } cout Please input this edge attaches two vertices sub