侧边栏壁纸
  • 累计撰写 247 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

最小生成树的定义和应用场景

kaixindeken
2021-04-23 / 0 评论 / 0 点赞 / 101 阅读 / 648 字

以无向图为例,如果图的任意两个顶点之间都是想通的,这个图就是连通图。
一个连通图的生成树是一个极小的连通子图,它含有图中全部的 n 个顶点,和足以构成一棵树的 n-1 条边,如下图所示:

1.png

图1是一个连通图,图2是该连通图的生成树,反过来说,如果一棵树大于 n-1 条边,则必然构成环。

前面我们也提到,带权的图叫做网,我们把构造连通网(带权连通图)的最小代价生成树叫做最小生成树。这个最小代价指的是通过 n-1 条边具有把 n 个顶点的连通图连接起来,并且使所有边的权值和最小。如下图所示,实线部分就是最小生成树:

1.png

最小生成树的应用场景很多,小到我们要来个欧洲十国游,怎么规划路径让交通费用最低,大到国家的电力网、公路网、通信网,怎么规划路径可以让建设成本最低,学习了最小生成树后,你就可以通过算法来计算出最佳路径了,不仅如此,所有涉及连接网络中所有节点的最优路径问题,都可以通过最小生成树来处理。

最小生成树有多种实现算法,我们这里介绍两种比较常见的:普里姆算法(Prim)和克鲁斯卡尔算法(Kruskal)。

0

评论区