Code Practice Journal | Day57_Graph07 Minimum Spanning Tree

1. 概念

生成树（Spanning Tree）

给定的图中选择一些边，使边连接图中所有节点但不成环，形成的子图即为生成树。

最小生成树（MST）

所有可能的生成树中，权重和最小的生成树即为最小生成树。

2. 算法

2.1 Kruskal

1、基本思想

对边按权重排序，注意加入边并保证不成环：
使用并查集来管理连接节点并检查是否成环

2、步骤：

对所有边按权重升序排列

初始化并查集

依次选择边，检查边的两个节点是否在统一连通分量中
在：跳过此边
不在：此边加入生成树，并合并两个节点所在连通分量

重复步骤

3、代码实现

class Program
{public class Edge : IComparable<Edge>{public int U, V, Weight;public Edge(int u, int v, int weight){U = u;V = v;Weight = weight;}public int CompareTo(Edge other){return Weight.CompareTo(other.Weight);}}public static int Find(int[] parent, int i){if (parent[i] == i)return i;return parent[i] = Find(parent, parent[i]);}public static void Union(int[] parent, int[] rank, int x, int y){int rootX = Find(parent, x);int rootY = Find(parent, y);if (rootX != rootY){if (rank[rootX] > rank[rootY]){parent[rootY] = rootX;}else if (rank[rootX] < rank[rootY]){parent[rootX] = rootY;}else{parent[rootY] = rootX;rank[rootX]++;}}}public static int KruskalMST(int V, List<Edge> edges){edges.Sort();int[] parent = new int[V + 1];int[] rank = new int[V + 1];for (int i = 1; i <= V; i++){parent[i] = i;rank[i] = 0;}int mstWeight = 0;foreach (var edge in edges){int u = edge.U;int v = edge.V;int w = edge.Weight;int rootU = Find(parent, u);int rootV = Find(parent, v);if (rootU != rootV){mstWeight += w;Union(parent, rank, rootU, rootV);}}return mstWeight;}public static void Main(string[] args){string[] firstLine = Console.ReadLine().Split();int V = int.Parse(firstLine[0]);int E = int.Parse(firstLine[1]);List<Edge> edges = new List<Edge>();for (int i = 0; i < E; i++){string[] edgeInput = Console.ReadLine().Split();int u = int.Parse(edgeInput[0]);int v = int.Parse(edgeInput[1]);int weight = int.Parse(edgeInput[2]);edges.Add(new Edge(u, v, weight));}Console.WriteLine(KruskalMST(V, edges));}
}

2.2 Prime

1、基本思想

从一个节点开始，逐步选择连接权重最小的边来扩展树：
已访问节点集合到未访问节点集合的最短距离

2、步骤：

选择一个起始节点，标记为已访问

将所有连接到已访问节点集合的边加入队列

从队列中选择权重最小的边，并检查这条边是否连接了一个未访问的节点
是：将该节点标记为已访问，加入已访问节点集合