图论算法（最小生成树介绍）

2022-04-20 IT知识

本文概述

树
生成树
生成树的属性
最小生成树

树树是具有以下属性的图：

图形已连接（可以从任何地方到任何地方）
没有循环（Acyclic）

文章图片

文章图片
生成树给定一个连接的无向图, 该图的生成树是一个子图, 该子图是一棵树, 并连接了所有顶点。单个图可以具有许多生成树。
例如：

文章图片
对于上面连接的图。可能有多个生成树, 例如

文章图片
生成树的属性

可能有几个具有最小权重的相同权重的最小生成树。
如果给定图的所有边缘权重都相同, 则该图的每个生成树都是最小的。
如果每个边缘都有不同的权重, 那么将只有一个唯一的最小生成树。
连通图G可以具有多个生成树。
断开连接的图不必覆盖树, 也可以不覆盖所有顶点。
生成树不包含循环。
生成树具有（n-1）个边, 其中n是顶点数。

甚至增加一个单边都会导致生成树失去其非周期性特性, 而消除一个单边会导致生成树失去连通性。
最小生成树 【图论算法（最小生成树介绍）】最小生成树是具有最小总成本的生成树。如果我们有一个链接的无向图, 其权重（或成本）与每个边结合。那么生成树的成本将是其边缘成本的总和。

文章图片

文章图片

推荐阅读

上一篇：N皇后问题和回溯算法

下一篇：最小生成树的应用