由于是无向无边权的联通图,故需要生成树的树高最小,等价于每个节点到根节点的距离尽量小,故可用 BFS 求单源最短路,所有点的距离最大者就是生成树的最小半径。可以吗
时间: 2024-03-29 15:38:23 浏览: 142
图的最小生成树prim算法
这种方法是可以求出生成树的半径,但是这个求解方法并不正确。
首先,如果使用 BFS 求单源最短路,得到的是以根节点为起点的最短路径,但不一定是以其他节点为起点的最短路径。因此,使用 BFS 得到的最长距离不一定是生成树的半径。
其次,即使使用 DFS 或者 Dijkstra 算法等其他求单源最短路的方法,也不能保证得到的最长距离一定是生成树的半径。因为生成树的半径并不一定是从根节点开始的最长路径。
因此,正确的求解方法应该是先使用 Prim 算法或者 Kruskal 算法得到最小生成树,然后再使用 BFS 或者其他方法求解树的直径,即树上任意两点之间的最长路径。这个最长路径即为生成树的半径。
阅读全文