图之--生成树和最小生成树

2020-10-03 本文已影响0人美雨知春

生成树：从无向图G中任一顶点V0出发，或者从有根邮箱图的跟V0出发，到图中其他各个顶点都存在路径
最小生成树：每个边有权值，不同的生成树权值不同，其中权值最小的生成树成为G的最小生成树（Minimum Spacing Tree，MST）
最小生成树有着广泛的应用，其算法有Kruskal和Prim算法