克鲁斯卡尔算法哪里出错了？？
[问题点数：20分，结帖人jianyuzhimei]
克鲁斯卡尔算法哪里出错了？？
[问题点数：20分，结帖人jianyuzhimei]
不显示删除回复
显示所有回复
显示星级回复
显示得分回复
只显示楼主
相关帖子推荐：
本帖子已过去太久远了，不再提供回复功能。你的位置： &&
算法：图解最小生成树之克鲁斯卡尔（Kruskal)算法
算法：图解最小生成树之克鲁斯卡尔（Kruskal)算法
我们在前面讲过的《克里姆算法》是以某个顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树的。同样的思路，我们也可以直接就以边为目标去构建，因为权值为边上，直接找最小权值的边来构建生成树也是很自然的想法，只不过构建时要考虑是否会形成环而已，此时我们就用到了图的存储结构中的边集数组结构，如图7-6-7 假设现在我们已经通过邻接矩阵得到了边集数组edges并按权值从小到大排列如上图。下面我们对着程序和每一步循环的图示来看：算法代码：typedef struct
/* 查找连线顶点的尾部下标 */
int Find(int *parent, int f)
while (parent[f] & 0)
f = parent[f];
/* 生成最小生成树 */
void MiniSpanTree_Kruskal(MGraph G)
int i, j, n ,
int k = 0;
int parent[MAXVEX];/* 定义一数组用来判断边与边是否形成环路 */
Edge edges[MAXEDGE];/* 定义边集数组,edge的结构为begin,end,weight,均为整型 */
/* 此处省略将邻接矩阵G转换为边集数组edges并按权由小到大排列的代码*/
for (i = 0; i & G.numV i++)
parent[i] = 0;
cout && "打印最小生成树：" &&
for (i = 0; i & G.numE i++)/* 循环每一条边 */
n = Find(parent, edges[i].begin);
m = Find(parent, edges[i].end);
if (n != m)/* 假如n与m不等，说明此边没有与现有的生成树形成环路 */
parent[n] =/* 将此边的结尾顶点放入下标为起点的parent中。 */
/* 表示此顶点已经在生成树集合中 */
cout && "(" && edges[i].begin && ", " && edges[i].end && ") "
&& edges[i].weight &&
}1、程序 第17～28行是初始化操作，中间省略了一些存储结构转换代码。2、第30～42行，i = 0 第一次循环，n = Find( parent, 4) = 4; 同理 m = 7; 因为 n != m 所以parent[4] = 7, 并且打印 “ (4, 7) 7 &” 。此时我们已经将边（v4, v7)纳入到最小生成树中，如下图的第一个小图。3、继续循环，当i从1 至 6 时，分别把（v2, v8), (v0, v1), (v0, v5), (v1, v8), (v3, v7), (v1, v6)纳入到最小生成树中，如下图所示，此时parent数组为{ 1, 5, 8, 7, 7, 8, 0, 0, 6 }，如何解读现在这些数字的意义呢？从图i = 6来看，其实是有两个连通的边集合A与B 纳入到最小生成树找中的，如图7-6-12所示。parent[0] = 1表示v0 和v1 已经在生成树的边集合A中，将parent[0] = 1中的 1 改成下标，由parent[1] = 5 ，表示v1 和v5 已经在生成树的边集合A中，parent[5] = 8 ，表示v5 和v8 已经在生成树的边集合A中，parent[8] = 6 ，表示v8 和v6 已经在生成树的边集合A中，parent[6] =0 表示集合A暂时到头，此时边集合A有 v0, v1, v5, v6, v8。查看parent中没有查看的值，parent[2] = 8，表明v2 和 v8在一个集合中，即A中。再由parent[3] = 7, parent[4] = 7 和 parent[7] = 0 可知v3, v4, v7 在一个边集合B中。4、当i = 7时， 调用Find函数，n = m = 6,不再打印，继续下一循环，即告诉我们，因为（v5, v6) 使得边集合A形成了回路，因此不能将其纳入生成树中，如图7-6-12所示。5、当i = 8时与上面相同，由于边(v1, v2) 使得边集合A形成了回路，因此不能将其纳入到生成树中，如图7-6-12所示。6、当i = 9时，n = 6, m = 7, 即parent[6] = 7，打印“（6， 7）19” ，此时parent数组为{ 1, 5, 8, 7, 7, 8, 7, 0, 6 } ，如图7-6-13所示。最后，我们来总结一下克鲁斯卡尔算法的定义：假设 N = （V, {E} ）是连通网，则令最小生成树的初始状态为只有n个顶点而无边的非连通图T { V, {} }，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将其加入到 T 中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。此算法的Find函数由边数e决定，时间复杂度为O(loge)，而外面有一个for循环e次，所以克鲁斯卡尔算法的时间复杂度为O(eloge)。对比普里姆和克鲁斯卡尔算法，克鲁斯卡尔算法主要针对边来展开，边数少时效率比较高，所以对于稀疏图有较大的优势；而普里姆算法对于稠密图，即边数非常多的情况下更好一些。
&&作者：Simba888888 &&
最新热门tag跪求 普里姆算法和克鲁斯卡尔算法_百度知道
跪求 普里姆算法和克鲁斯卡尔算法
我们的课程设计，哎，怪只怪小弟弟平时没有学好，弄了好久都不行，所以请各路大侠来帮我解决一下，跪谢，尽快！！！要用 C语言写，要可以运行的，界面比较友好久可以，没有其他要求。100分不成敬意！！！！！！！．以邻接矩表的方式确定一个图，完成：⑴建立并显示出它的邻接链表；⑵分别用普里姆算法和克鲁斯卡尔算法构造其最小生成树，随时显示其构造的过程；⑶给出某一确定顶点到所有其它顶点的最短路径；
#include&stdio.h&#include&malloc.h&#define MAXVEX 100#define MAX 1000#include&string.h&typedef struct ArcCell
// 用1表示相邻,0表示不相邻；
// 该弧的权值 }arc[MAXVEX][MAXVEX];
// 弧的结构typedef struct {
vexs[MAXVEX];
// 顶点信息
// 弧的信息
// 顶点数，弧数
// 图的结构void createMGraph(MGraph *G)
//建无向网的邻接矩阵存储结构{
int i,j,k,W= 0; printf(& 请输入图中的顶点数和弧数：&); scanf(&%d %d&,&(G-&n),&(G-&e)); printf(&\n 请输入各个结点的名称: &); for(i=0; i&G-&n; i++)
getchar();
scanf(&%c&,&(G-&vexs[i])); } for(i=0; i&G-&n; i++)
for(j=0; j&G-&n; j++)
G-&arcs[i][j].adj = 0;
if(i!=j) G-&arcs[i][j].w=MAX;
else G-&arcs[i][j].w=0;
} printf(&\n 请依次输入这%d条弧的起点，终点和权值:&,G-&e); for(k=0; k&G-&e; k++) {
int h = k+1;
printf(&\n 第%d条弧:&,h);
scanf(&%d %d %d&,&i,&j,&W);
G-&arcs[i][j].w = W;
G-&arcs[i][j].adj = 1;
G-&arcs[j][i].w = W;
G-&arcs[j][i].adj = 1; }}
void MinSpanTree_prim(MGraph* G)
//Prim算法生成最小生成树{ int vexnum=G-&n; int lowcost[100],closest[100]; int i,j,k, for(i = 0;i&i++) {
lowcost[i] = G-&arcs[0][i].w;
closest[i] = 0; } closest[0] = -1; for(i = 1;i&i++) {
min = MAX;
for(j = 0;j&j++)
if(closest[j] != -1&&lowcost[j]&min)
min = lowcost[j];
printf(&(%c,%c) %d \n&,G-&vexs[closest[k]],G-&vexs[k],lowcost[k]);
closest[k] = -1;
for(j = 1;j&j++)
if((closest[j]!=-1)&&(G-&arcs[k][j].w&lowcost[j]))
lowcost[j] = G-&arcs[k][j].w;
closest[j] =
} }}void main(){ MGraph G;
createMGraph(&G); printf(& 最小生成树的边以及权值为:\n&); MinSpanTree_prim(&G);}c++的，不过你改成C的也应该可以用行吧~~
其他类似问题
普里姆算法的相关知识
按默认排序
其他2条回答
北大数学系主页上有，尊重版权，不拷过来了
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁c语言 克鲁斯卡尔算法，怎么判断是否构成回路、详细通俗点。。谢谢
c语言 克鲁斯卡尔算法，怎么判断是否构成回路、详细通俗点。。谢谢 30
我主要是不知道怎么判断是否构成回路、书上说把一个顶点看做是一个树根、把顶点的双亲构造成一颗树，双亲置-1。当树的根相同时，说明两个顶点在一个连通分量里面，不可取。但我着实没懂什么意思？是把顶点作为根，当这个顶点和另一个顶点的最短权值边不构成回路时，把一个顶点作为另一个顶点的孩子吗？把另一个顶点的双亲置为这个顶点？是不是这样理解点、求解，最好配上代码
不区分大小写匿名
等待您来回答
编程领域专家}