数据结构的“图的生成树”是如何定义的?
发布网友
发布时间：2022-04-23 22:54
共3个回答
热心网友
时间：2022-04-27 19:48
定义1：对于无向图G和一棵树T来说，如果T是G的子图，则称T为G的树，如果T是G的生成子图，则称T是G的生成树。
定义2：对于一个边上具有权值的图来说，其边权值和最小的生成树称做图G的最小生成树。
若一个无向图G的生成子图是一棵树，则称之为G的生成树。连通且不含圈的无向图如城市煤气、自来水管道网络，铁路的专用线网等，都可以用树的形式来表示。
扩展资料：
最小树形图基于贪心的思想和缩点的思想，将几个点看成一个点，所有连接到这几个点的边都视为连到收缩点，所以从这几个点连出的边都被视为从收缩点连出；次小生成树的边的权值和可能等于最小生成树的权值和，或者略大。
对于一个连通网（即连通带权图，假定每条边上的权值均为正实数）来说生成树不同，每棵树的权（即树中所有边上的权值总和）也可能不同。
参考资料来源：
百度百科-图的生成树
热心网友
时间：2022-04-27 21:06
一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。
热心网友
时间：2022-04-27 22:41
生成树定义：
设图 G=(V, E) 是个连通图，当从图任一顶点出发遍历图G 时，将边集 E(G) 分成两个集合 T(G) 和 B(G)。其中 T(G)是遍历图时所经过的边的集合，B(G) 是遍历图时未经过的边的集合。显然，G1(V, T) 是图 G 的极小连通子图，即子图G1 是连通图 G 的生成树。
最小生成树 ：
给定一个无向网络，在该网的所有生成树中，使得各边权数之和最小的那棵生成树称为该网的最小生成树。
深度优先生成森林：
连通图的生成树不一定是唯一的，不同的遍历图的方法得到不同的生成树;从不同的顶点出发可得到不同的生成树。
连通图本身就是连通分量，其中顶点集+遍历经过的边=生成树。
非连通图的生成森林不一定是唯一的。
非连通图各个连通分量的顶点集+遍历时经过的边=若干颗生成树（生成森林）
