kruskal(mgraph g)

kruskal算法是一种用于解决最小生成树问题的贪心算法。给定一个连通的加权无向图g和其边集E，kruskal算法的目标是找到一个最小的生成树，即包含图中所有顶点，且所有边的权值之和最小的树。

具体步骤如下：
1. 将图中的边按照权值从小到大进行排序。
2. 创建一个空的集合U，用于保存最小生成树的边。
3. 遍历排序后的边集，对于每一条边e，判断它的两个顶点是否在U中。
- 若两个顶点都不在U中，将这条边加入U。
- 若其中一个顶点在U中，跳过该边。
- 若两个顶点都在U中，形成回路，跳过该边。
4. 重复步骤3，直到U中的边数等于顶点数减一，表示找到了一个最小生成树。
5. 返回U中的边作为最小生成树的边集。

kruskal算法的关键是通过检查边的两个顶点是否在同一集合中来判断是否形成回路，可以使用并查集数据结构来实现。并查集维护了一个集合的分区，其中每个元素都有一个指向其根节点的指针，根节点的指针指向自身，可以使用路径压缩和按秩合并来优化并查集的效率。

kruskal算法的时间复杂度主要取决于对边的排序操作，为O(ElogE)，其中E为边的数量。

相关问题

void MinTree_Kruskal(MGraph G) { //kruskal算法运用并查集知识 KEdge h[MAXNUM]; //存储边信息 int fat[MAX]; //fat[i]存储i的前驱结点 int x,y; int i,j,k=1; int has=0; //已经连接了多少条边 int minprice=0; for(i=1; i<=G.vexnum; i++) //初始化 { for(j=i; j<=G.vexnum; j++) { if(G.arcs[i][j].adj!=INFINITY) { h[k].a=i; h[k].b=j; h[k].w=G.arcs[i][j].adj; k++; } } } for(i=1; i<=G.vexnum; i++) //初始化 { fat[i]=i; } Sort(h,G.arcnum); //kruskal思想，排序权值 printf("使用kruskal算法得到的最小生成树的各边及其权值为:\n\n"); printf(" 结点 权值\n"); for(i=1; i<=G.arcnum; i++) { if(has==G.vexnum-1) break;//树的边数等于顶点-1 x=Root(h[i].a,fat); //寻找根结点 y=Root(h[i].b,fat); //寻找根结点 if(x!=y) //不在一个集合 { Unionn(x,y,fat); printf("%3c--%c%8d\n",G.vexs[h[i].a],G.vexs[h[i].b],h[i].w); minprice+=h[i].w; has++; } } printf("\n\n使用kruskal算法得到的最小生成树的代价为: %d \n",minprice); }代码分析

这段代码实现了最小生成树的 Kruskal 算法。具体实现过程如下：

- 定义 KEdge 类型，用于存储边信息，包括边的起点、终点和权值。
- 定义 fat 数组，表示每个节点的前驱结点，初始化为节点本身。
- 将所有边信息存储到 h 数组中，并按照权值从小到大排序。
- 依次遍历 h 数组中的每条边，如果当前已经连接的边数等于总节点数-1，则退出循环。
- 对于每条边，通过 Root 函数查找其起点和终点所在的集合的根节点，如果不在同一个集合中，则将它们合并，并输出该边的信息。
- 最后输出最小生成树的代价。

其中，Root 和 Unionn 函数是对并查集的操作，用于查找根节点和合并两个集合。

void Kruskal(MGraph &G) //克鲁斯卡尔算法 { int i,j,u1,v1,sn1,sn2,k; int vset[M]; Edge E[M]; k=0; for (i=0;i<G.n;i++) { for (j=0;j<G.n;j++) { if (G.edeges[i][j]!=0&&G.edeges[i][j]!=N) { E[k].u=i; E[k].v=j; E[k].w=G.edeges[i][j]; k++; } } } InsertSort(E,G.e); for (i=0;i<G.n;i++) vset[i]=i; k=1; j=0; while (k<G.n) { u1=E[j].u; v1=E[j].v; sn1=vset[u1]; sn2=vset[v1]; if (sn1!=sn2) { printf("<%c,%c>:%d\n",G.vexs[u1],G.vexs[v1],E[j].w); k++; for (i=0;i<G.n;i++) { if (vset[i]==sn2) { vset[i]=sn1; } } } j++; } }这一部分的源代码哪里出错了

这段代码实现了最小生成树的 Kruskal 算法，但是在代码中有一些拼写错误，需要进行修改:

1. 在第 5 行，将 `int vset[M];` 改为 `int vset[N];`，因为节点数是 N 而不是 M。

2. 在第 23 行，将 `InsertSort(E,G.e);` 改为 `InsertSort(E,G.e_num);`，因为 `e_num` 才是边数。

3. 在第 30 行，将 `printf("<%c,%c>:%d\n",G.vexs[u1],G.vexs[v1],E[j].w);` 改为 `printf("<%c,%c>:%d\n",G.vertex[u1],G.vertex[v1],E[j].weight);`，因为 `vertex` 才是顶点数组，`weight` 才是边权值。

修改后的代码如下：

void Kruskal(MGraph &G)       //克鲁斯卡尔算法
{
    int i,j,u1,v1,sn1,sn2,k;
    int vset[N];
    Edge E[M];
    k=0;
    for (i=0;i<G.n;i++)
    {
        for (j=0;j<G.n;j++)
        {
            if (G.edges[i][j]!=0&&G.edges[i][j]!=N)
            {
                E[k].u=i;
                E[k].v=j;
                E[k].weight=G.edges[i][j];
                k++;
            }
        }
    }
    InsertSort(E,G.e_num);
    for (i=0;i<G.n;i++)
        vset[i]=i;
    k=1;
    j=0;
    while (k<G.n)
    {
        u1=E[j].u;
        v1=E[j].v;
        sn1=vset[u1];
        sn2=vset[v1];
        if (sn1!=sn2)
        {
            printf("<%c,%c>:%d\n",G.vertex[u1],G.vertex[v1],E[j].weight);
            k++;
            for (i=0;i<G.n;i++)
            {
                if (vset[i]==sn2)
                {
                    vset[i]=sn1;
                }
            }
        }
        j++;
    }
}