Net Core教程

【C# 数据结构与算法】 最小生成树

本文主要是介绍【C# 数据结构与算法】 最小生成树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

 概览

 

 概念

最小生成树是一副连通加权无向图中一棵权值最小的生成树。

 

在一给定的无向图 G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即 ( u , v ) ∈ E {\displaystyle (u,v)\in E} (u,v)\in E），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即 T ⊆ E {\displaystyle T\subseteq E} T\subseteq E）且 (V, T) 为树，使得

w ( T ) = ∑ ( u , v ) ∈ T w ( u , v ) {\displaystyle w(T)=\sum _{(u,v)\in T}w(u,v)} w(T)=\sum _{(u,v)\in T}w(u,v)

的 w(T) 最小，则此 T 为 G 的最小生成树。

最小生成树其实是最小权重生成树的简称。

一个连通图可能有多个生成树。当图中的边具有权值时，总会有一个生成树的边的权值之和小于或者等于其它生成树的边的权值之和。广义上而言，对于非连通无向图来说，它的每一连通分量同样有最小生成树，它们的并被称为最小生成森林。

以有线电视电缆的架设为例，若只能沿著街道布线，则以街道为边，而路口为顶点，其中必然有一最小生成树能使布线成本最低。

 

这篇关于【C# 数据结构与算法】 最小生成树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航