04最小生成树
# 最小生成树问题
参考链接:https://blog.csdn.net/Africa_South/article/details/88608619
一个连通图的生成树是一个极小连通子图,它含有图中全部的顶点,但是只有足有构成一棵树的n-1条边。它有如下性质:
- 一棵有n个顶点的生成树有且只有n − 1条边;
- 如果一个图有n个顶点和小于n − 1条边,则是非连通图;如果它多于n − 1条边,则一定有环;
- 但是有n − 1条边的n个顶点的图不一定是生成树。(它只是必要条件)
一棵生成树的代价就是树上各边的代价之和。
最小生成树就是构造连通图的最小代价生成树,简称为最小生成树。
# Prim算法
# Kruskal算法
上次更新: 2023/11/19, 12:55:48