二叉树 - c++数据结构 最小生成树题目

Question

原题：The radius of a tree is the maximum distance from the root to a leaf. Given a connected, undirected graph, write a procedure to find a spanning tree of minimum radius.
(Hint: use breadth-first search)

思路？？？

Answer 1

Tip: Use breadth-first algorithm (basically ensures that the generated tree has a minimum radius)

Basically traverse the graph breadth-first, then put the traversed nodes on the tree and mark them so that you don’t visit the traversed nodes next time. You can consider using a linked list to store visited nodes.

Answer 2

You can first read the explanations of BFS and DFS and related implementations on Wikipedia.

Starting from the root node, find the nearest and unvisited node each time. Next time start with all these nodes and continue repeating the above process.

Minimum spanning tree can also refer to the related algorithms of MST, prim, kruskal (I don’t know if there are any spelling errors).

Read more classic questions, and similar problems like this will be easily solved.

Answer 3

Isn’t it a minimum radius spanning tree after running BFS?
Use adjacency list to save the image.vector<int>g[SIZE].
There is also a minimum spanning tree (generally refers to the smallest value)