当前位置: 首页 > news >正文

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));}
}

http://www.mrgr.cn/news/14996.html

相关文章:

  • 概率论与编程的联系及数据科学应用
  • HTTP 之 HTTP头部优化策略(九)
  • 基于vue框架的餐馆管理系统jo0i7(程序+源码+数据库+调试部署+开发环境)系统界面在最后面。
  • C++竞赛初阶L1-14-第六单元-数组(31~33课)547: T456477 查找特定的值
  • 数据库——开篇
  • 2-80 基于matlab-GUI,实现kalman滤波对目标物的位置进行检测跟踪
  • kafka集群
  • Windows中Git对文件名大小写不敏感的问题解决方法
  • 【区块链 + 司法存证】神州契信区块链电子签约系统 | FISCO BCOS应用案例
  • java调用opencv的流程
  • 基于SpringBoot+Vue+MySQL的图书管理系统
  • 如何从头开始编写一个简单的 RPC 协议(手写 Dubbo 的自定义协议)
  • 【数模修炼之旅】10 遗传算法 深度解析(教程+代码)
  • 【PostgreSQL教程】PostgreSQL 高级篇之 视图
  • 【Java EE】JVM
  • OpenHarmony 实战开发——应用HAP包签名
  • 光学涡旋Talbot阵列照明器的matlab模拟与仿真
  • 【香橙派系列教程】(二十) 系统移植、交叉编译工具链—OrangePi Zero2 SDK说明
  • 100Kg大载重6轴共桨多旋翼无人机技术详解
  • 探索AWS EC2:提升企业云计算能力的理想选择