最小生成树(C语言, kruskal算法)

  /*
   * kruskal算法，边集数组, 无向图，最小生成树，贪心算法
   * 代码实现<<大话数据结构>>图7-6-7(和prim算法用的同一张图)
   * 最终成生n-1条边的树，路径权值和最小
   */

// 边集数组的节点
typedef struct {
    int begin;
    int end;
    int weight;
}NODE, *PNODE;

// 此函数的功能是根据parent数组找到所属连通分量（子图）的边界下标，如果n，m返回的数值相同，则说明他们已经在同一生成树中，不应该有新的连线，否则成为环路
int Find(int *parent, int f)
{
    while( parent[f] > 0 ) //终止条件
    {
        f = parent[f];
    }
    return f;
}

void MiniSpanTree_Kruskal(MGraph G)
{
    int i, n, m;
    Edge edges[MAGEDGE];    // 边集数组
    int parent[MAXVEX];     // 一个可以找到所属连通分量边界节点下标的数组（下标和值组成了类似单链表的功能）

    for( i=0; i < G.numVertexes; i++ )
    {
        parent[i] = 0; // 初始化
    }

    for( i=0; i < G.numEdges; i++ )
    {
        n = Find(parent, edges[i].begin);   // 4 2 0 1 5 3 8 6 6 6 7
        m = Find(parent, edges[i].end);     // 7 8 1 5 8 7 6 6 6 7 7

        if( n != m )        // 如果n==m，则形成环路，这两个节点已经是同一连通分量（集合）
        {
            parent[n] = m;  // 更新数组，纳入新节点到连通分量（集合）中
            printf("(%d, %d) %d ", edges[i].begin, edges[i].end, edges[i].weight);
        }
    }
}

最小生成树(C语言, kruskal算法)

原文：https://blog.51cto.com/sndapk/2702043