二叉树 - 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

提示：用廣度優先演算法（基本上可以保證產生的樹有minimum radius）

基本上就是廣度優先遍歷這張圖，然後把遍歷過的節點放到樹上，並且標記下來，下次不要再訪問遍歷過的節點。可以考慮用個鍊錶來儲存造訪過的節點。

Answer 2

可以先閱讀wikipedia上關於BFS和DFS的解釋以及相關的實作。

從根節點開始，每次找到最近的且沒有訪問過的節點。下次從所有這些節點開始，繼續重複上述過程。

最小生成樹也可以參考MST的相關演算法，prim，kruskal（不知道有沒有拼字錯誤）。

經典問題多看，這種相類似的問題就會迎刃而解。

Answer 3

BFS跑一遍不就是一個最小半徑生成樹了麼？
使用鄰接表存圖吧.vectorg[SIZE].
還有最小生成樹（一般指的是value最小）