FC08-Kruskal算法：求无向图的最小生成树¶

代码实现¶

C
// 全局并查集数组（已在外部定义）
extern int parent[MAX_SIZE];


/**
 * Kruskal算法：基于邻接表构建最小生成树
 * @param G 邻接表表示的无向连通图
 */
void Kruskal(ALGraph* G) {
    int n = G->n;
    int totalEdges = 0;
    Edge edges[MAX_SIZE * MAX_SIZE];  // 最多边数

    // Step 1: 遍历邻接表，提取所有 u < v 的边（避免重复）
    for (int u = 0; u < n; u++) {
        ArcNode* p = G->adjlist[u].firstarc;
        while (p != NULL) {
            int v = p->adjvex;
            int w = p->weight;
            if (u < v) {  // 无向图，只存一次 u-v
                edges[totalEdges++] = (Edge){u, v, w};
            }
            p = p->next;
        }
    }

    // Step 2: 按边权排序
    qsort(edges);

    // Step 3: 初始化并查集
    init();

    // Step 4: 开始贪心选边
    int mstWeight = 0;
    int mstEdges = 0;

    printf("最小生成树包含的边：");

    for (int i = 0; i < totalEdges; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].w;

        int rootU = find(u);
        int rootV = find(v);

        if (rootU != rootV) {
            // 不在同一集合，不会成环
            unionSet(u, v);           // 合并集合
            printf("%d-%d:%d ", u, v, w);
            mstWeight += w;
            mstEdges++;
        }

        // MST 只需要 n-1 条边
        if (mstEdges == n - 1) break;
    }

    printf("\n最小生成树总权重：%d\n", mstWeight);

    // 检查连通性
    if (mstEdges < n - 1) {
        printf("⚠️  图不连通，无法生成完整最小生成树！\n");
    } else {
        printf("✅ 最小生成树已完整生成。\n");
    }
}

代码逻辑解析¶

1. Kruskal算法基本思想¶

将图中所有边按权值从小到大排序
依次选择权值最小的边
如果选择的边不会在当前生成树中形成环，则将其加入生成树
重复此过程直到生成树包含 n-1 条边

2. 并查集（Union-Find）数据结构¶

作用：高效检测添加某条边是否会形成环
find操作：查找某个顶点所属集合的根节点
union操作：合并两个不同的集合

3. 算法步骤详解¶

步骤1：初始化并查集¶

C
// 每个顶点初始时都是独立的集合
for (int i = 0; i < G.numver; i++) {
    parent[i] = i; // 每个顶点的父节点是自己
}

步骤2：边排序¶

C
// 使用直接插入排序按边权值升序排列
for (int i = 2; i <= G.numedg; i++) {
    // 插入排序的核心逻辑
}

步骤3：逐边处理¶

C
for (int i = 1; i <= G.numedg; i++) {
    // 检查是否形成环
    // 如果不形成环，则加入生成树
    // 合并集合
}

时间复杂度分析¶

1. 排序阶段¶

使用直接插入排序：O(E²)
其中 E 是边数

2. 处理边阶段¶

外层循环：O(E)
每次 find 操作：O(V)（最坏情况）
总计：O(E × V)

3. 总体时间复杂度¶

O(E²)（主要由插入排序决定）

4. 优化可能性¶

使用快速排序或堆排序：O(E log E)
使用路径压缩和按秩合并优化并查集：find 操作接近 O(1)
优化后时间复杂度：O(E log E)

空间复杂度分析¶

1. 额外数组空间¶

parent[] 数组：O(V)
其中 V 是顶点数

2. 局部变量¶

常量级别的额外空间

3. 总体空间复杂度¶

O(V)

较难理解部分的说明¶

1. 并查集的工作原理¶

C
// 并查集的两个核心操作：

// 1. 查找操作：找到某个元素所在集合的代表元素（根节点）
int find(int v, int parent[]) {
    while (parent[v] != v) {  // 沿着父节点链向上查找
        v = parent[v];
    }
    return v;
}

// 2. 合并操作：将两个集合合并
parent[root1] = root2;  // 将一个集合的根连接到另一个集合的根

图解说明：¶

假设初始状态（4个顶点）：

Text Only
1 2	`parent = [0, 1, 2, 3] 集合：{0} {1} {2} {3}`

处理边 0-1：

Text Only
1 2 3 4	`find(0) = 0, find(1) = 1 // 不同集合合并：parent[0] = 1 parent = [1, 1, 2, 3] 集合：{0,1} {2} {3}`

处理边 2-3：

Text Only
1 2 3 4	`find(2) = 2, find(3) = 3 // 不同集合合并：parent[2] = 3 parent = [1, 1, 3, 3] 集合：{0,1} {2,3}`

处理边 1-3：

Text Only
1 2 3 4	`find(1) = 1, find(3) = 3 // 不同集合合并：parent[1] = 3 parent = [1, 3, 3, 3] 集合：{0,1,2,3} // 所有顶点在同一集合`

2. 环检测机制¶

当处理一条边时： - 如果边的两个端点已经在同一集合中，说明添加这条边会形成环 - 如果边的两个端点在不同集合中，添加这条边不会形成环

3. 排序算法详解¶

直接插入排序过程：

C
// 对边按权值排序
for (int i = 2; i <= G.numedg; i++) {
    G.A[0] = G.A[i];        // 取出当前边
    int j = i - 1;

    // 向前查找插入位置
    for (; j >= 1 && G.A[0].weight < G.A[j].weight; j--) {
        G.A[j + 1] = G.A[j]; // 元素后移
    }

    G.A[j + 1] = G.A[0];    // 插入到正确位置
}

延伸知识点¶

1. 优化版本 - 使用快速排序和路径压缩¶

C
// 优化的find操作（路径压缩）
int findOptimized(int v, int parent[]) {
    if (parent[v] != v) {
        parent[v] = findOptimized(parent[v], parent); // 路径压缩
    }
    return parent[v];
}

// 使用快速排序优化
void quickSort(Edge A[], int low, int high) {
    if (low < high) {
        int pivot = partition(A, low, high);
        quickSort(A, low, pivot - 1);
        quickSort(A, pivot + 1, high);
    }
}

void KruskalOptimized(EGraph G) {
    int parent[G.numver];
    for (int i = 0; i < G.numver; i++) {
        parent[i] = i;
    }

    // 快速排序
    quickSort(G.A, 1, G.numedg);

    int edgeCount = 0;
    for (int i = 1; i <= G.numedg && edgeCount < G.numver - 1; i++) {
        int root1 = findOptimized(G.A[i].start, parent);
        int root2 = findOptimized(G.A[i].end, parent);

        if (root1 != root2) {
            printf("%d-%d:%d ", G.A[i].start, G.A[i].end, G.A[i].weight);
            parent[root1] = root2;
            edgeCount++;
        }
    }
}

2. Prim算法与Kruskal算法对比¶

特性	Prim算法	Kruskal算法
基本思想	基于顶点的贪心策略	基于边的贪心策略
时间复杂度	O(V²) 或 O(E log V)	O(E log E)
空间复杂度	O(V)	O(V)
适用场景	稠密图	稀疏图
数据结构	邻接矩阵/邻接表	边集数组
环检测	不需要（总是安全添加）	并查集

3. 实际应用场景¶

网络设计：通信网络、电力网络的最小成本连接
交通规划：道路系统建设的最小成本方案
电路设计：电子电路板的最小布线
图像处理：图像分割和边缘检测
社交网络：社区发现和网络分析

4. 相关算法扩展¶

C
// 最小生成树的性质验证
bool isMST(EGraph G, Edge selectedEdges[], int edgeCount) {
    // 验证边数是否为V-1
    if (edgeCount != G.numver - 1) return false;

    // 验证是否连通（使用并查集）
    int parent[G.numver];
    for (int i = 0; i < G.numver; i++) {
        parent[i] = i;
    }

    for (int i = 0; i < edgeCount; i++) {
        int root1 = find(selectedEdges[i].start, parent);
        int root2 = find(selectedEdges[i].end, parent);
        if (root1 != root2) {
            parent[root1] = root2;
        }
    }

    // 检查是否所有顶点在同一集合
    int root = find(0, parent);
    for (int i = 1; i < G.numver; i++) {
        if (find(i, parent) != root) {
            return false;
        }
    }

    return true;
}

// 次小生成树
int secondMST(EGraph G) {
    // 1. 先求最小生成树
    // 2. 对每条MST中的边，暂时删除
    // 3. 重新求MST，记录最小值
    // 4. 恢复删除的边
}

5. 并查集的进一步优化¶

C
// 按秩合并优化
typedef struct {
    int parent;
    int rank; // 树的高度上界
} UnionFindNode;

void unionByRank(UnionFindNode nodes[], int x, int y) {
    int rootX = find(x, nodes);
    int rootY = find(y, nodes);

    if (rootX != rootY) {
        // 将秩小的树连接到秩大的树下
        if (nodes[rootX].rank < nodes[rootY].rank) {
            nodes[rootX].parent = rootY;
        } else if (nodes[rootX].rank > nodes[rootY].rank) {
            nodes[rootY].parent = rootX;
        } else {
            nodes[rootY].parent = rootX;
            nodes[rootX].rank++;
        }
    }
}

Kruskal算法体现了贪心策略和并查集数据结构的完美结合，通过巧妙地使用并查集来检测环的存在，实现了高效的最小生成树构建，是图论算法中的经典之作。