已掌握邻接矩阵实现，求C语言邻接表版Prim与Kruskal算法方案

Prim算法核心是维护一个已选顶点集合，每次选择连接集合内外权重最小的边。用邻接表实现时，无需依赖二维矩阵，改用以下结构和步骤：

• 邻接表结构：用数组或链表存储每个顶点的邻接边，每条边包含目标顶点和权重。例如adj[u]是一个列表，每个元素为(v, weight)。
• 维护两个一维数组：
  • key[]：记录每个顶点到已选集合的最小权重，初始时除起始顶点设为0，其余设为无穷大。
  • inMST[]：标记顶点是否已加入最小生成树，初始全为false。
• 执行步骤：
  1. 初始化key和inMST数组，选定起始顶点（如0）的key为0。
  2. 循环n次（n为顶点总数）：
     • 找到inMST为false且key值最小的顶点u。
     • 将u标记为inMST=true，累计其key值到MST总权重。
     • 遍历adj[u]中的所有边(v, w)：若v未加入MST且w < key[v]，则更新key[v] = w。
• 优化技巧：用最小堆（优先队列）存储(key值, 顶点)，可快速找到最小key的顶点，弹出堆顶时需检查inMST状态，避免处理已加入MST的旧数据。

Kruskal算法核心是按权重排序所有边，通过并查集（Union-Find）筛选不形成环的边。邻接表的作用是收集全局边列表，具体步骤：

• 提取边集：遍历邻接表，将所有边整理为(权重, u, v)的格式，无向图中需避免重复（如仅存储u < v的边）。
• 排序边集：将所有边按权重从小到大排序。
• 初始化并查集：每个顶点独立为一个集合，维护parent[]（记录父节点）和rank[]（用于按秩合并优化）。
• 筛选有效边：遍历排序后的边，对每条边(w, u, v)：
  • 用并查集查询u和v的根节点。
  • 若根节点不同，说明加入该边不会形成环，将其加入MST并合并两个顶点的集合。
  • 累计n-1条边后（n为顶点数），停止遍历。

Prim算法伪代码 #

function prim(adj, n):
    key = [infinity] * n
    inMST = [false] * n
    key[0] = 0
    mst_total = 0

    for i in range(n):
        // 找到未加入MST的最小key顶点
        u = -1
        min_key = infinity
        for j in range(n):
            if not inMST[j] and key[j] < min_key:
                min_key = key[j]
                u = j
        if u == -1:
            break // 图不连通，无法生成完整MST
        
        inMST[u] = true
        mst_total += min_key

        // 更新邻接顶点的key值
        for (v, weight) in adj[u]:
            if not inMST[v] and weight < key[v]:
                key[v] = weight
    return mst_total

Kruskal算法伪代码 #

// 并查集核心函数
function find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x]) // 路径压缩
    return parent[x]

function union(parent, rank, x, y):
    x_root = find(parent, x)
    y_root = find(parent, y)
    if x_root == y_root:
        return false // 已在同一集合，合并失败
    
    // 按秩合并
    if rank[x_root] < rank[y_root]:
        parent[x_root] = y_root
    else:
        parent[y_root] = x_root
        if rank[x_root] == rank[y_root]:
            rank[x_root] += 1
    return true

function kruskal(adj, n):
    edges = []
    // 提取无重复边
    for u in range(n):
        for (v, weight) in adj[u]:
            if u < v:
                edges.append( (weight, u, v) )
    // 按权重排序
    edges.sort()
    
    parent = [i for i in range(n)]
    rank = [0] * n
    mst_total = 0
    edge_count = 0

    for (weight, u, v) in edges:
        if union(parent, rank, u, v):
            mst_total += weight
            edge_count += 1
            if edge_count == n-1:
                break
    return mst_total

内容的提问来源于stack exchange，提问作者user20532639