本文共 2348 字，大约阅读时间需要 7 分钟。
Prim算法与Kruskal算法是解决最小生成树问题的经典方法，两者各有特点且在实现上有显著差异。以下将分别阐述Prim算法和Kruskal算法的核心思想、代码实现及其适用场景。
Prim算法通过每次选择一条连接当前树的外点（不形成环）并加入树中，直到所有节点纳入树中。其关键步骤包括：
示例代码（伪代码）：
// 读取输入：n为节点数，m为边数，G为邻接矩阵n, m = 读取输入G = 初始化邻接矩阵lowcost = [INF] * (n + 1)mst = [0] * (n + 1) // 记录每个点的父节点visited = [False] * (n + 1)sum = 0起点 = 1lowcost[起点] = 0visited[起点] = Truemst[起点] = 0while 有未访问点： min_cost = INF min_point = -1 for j from 2到n: if not visited[j] and lowcost[j] < min_cost: min_cost = lowcost[j] min_point = j if min_point == -1: break // 图不连通 visited[min_point] = True sum += min_cost for j from 2到n: if not visited[j]: if G[min_point][j] < lowcost[j]: lowcost[j] = G[min_point][j] mst[j] = min_pointreturn mst, sum
Kruskal算法通过先对所有边按权值排序，然后每次选择权值最小的未被选的边，若该边的两端点不在同一个连通分量中，则将它们合并到同一连通分量中。其关键步骤包括：
示例代码（伪代码）：
// 读取输入：n为节点数，m为边数// 为每条边创建对象，包含u, v, w属性edges = []for _ in range(m): u, v, w = 读取输入 edges.append( (w, u, v) )// 间接排序：根据边的权重对r数组进行排序（避免直接操作边数组）r = list(range(m))w = [e[0] for e in edges]// Filmsort：间接排序def cmp(i, j): if edges[i][0] < edges[j][0]: return -1 return 1sort(r, key=cmp)edges_sorted = [ (w[i], u[i], v[i]) for i in r ]父 = [i for i in range(n + 1)]rank = [1] * (n + 1)def find(u): while 父[u] != u: father = parent[u] u = father return udef union(u, v): u_root = find(u) v_root = find(v) if u_root == v_root: return False if rank[u_root] < rank[v_root]: parent[u_root] = v_root rank[v_root] += rank[u_root] else: parent[v_root] = u_root rank[u_root] += v_root return Truemst = []sum = 0for w, u, v in edges_sorted: if parent[u] != parent[v]: union(u, v) sum += w mst.append( (u, v) ) if len(mst) == n - 1: breakreturn mst, sum
以下是一些经典的最少生成树问题：
通过掌握这两种方法，你可以任意处理给定的图，将其转化为最小生成树并计算权重总和。这对你的学习和解决实际问题具有重要意义。
转载地址：http://vcfmz.baihongyu.com/