本文主要是介绍Code Practice Journal | Day56_Graph06 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、步骤：
选择一个起始节点，标记为已访问
将所有连接到已访问节点集合的边加入队列
从队列中选择权重最小的边，并检查这条边是否连接了一个未访问的节点
是：将该节点标记为已访问，加入已访问节点集合
重复步骤
3、代码实现
class Program
{public class Edge{public int V, Weight;public Edge(int v, int weight){V = v;Weight = weight;}}public static int PrimMST(int V, List<Edge>[] graph){bool[] visited = new bool[V + 1];int[] minEdge = new int[V + 1];for (int i = 1; i <= V; i++)minEdge[i] = int.MaxValue;int mstWeight = 0;minEdge[1] = 0;for (int i = 0; i < V; i++){int v = -1;for (int j = 1; j <= V; j++){if (!visited[j] && (v == -1 || minEdge[j] < minEdge[v]))v = j;}if (minEdge[v] == int.MaxValue)return -1;mstWeight += minEdge[v];visited[v] = true;foreach (var edge in graph[v]){if (!visited[edge.V] && edge.Weight < minEdge[edge.V]){minEdge[edge.V] = edge.Weight;}}}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>[] graph = new List<Edge>[V + 1];for (int i = 1; i <= V; i++)graph[i] = 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]);graph[u].Add(new Edge(v, weight));graph[v].Add(new Edge(u, weight));}Console.WriteLine(PrimMST(V, graph));}
}这篇关于Code Practice Journal | Day56_Graph06 Minimum Spanning Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
