二叉树 - c++数据结构 最小生成树题目
大家讲道理
大家讲道理 2017-04-17 13:15:17
0
3
601

原题: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)

思路???

大家讲道理
大家讲道理

光阴似箭催人老,日月如移越少年。

reply all(3)
巴扎黑

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.

阿神

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.

Peter_Zhu

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)

Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template
About us Disclaimer Sitemap
php.cn:Public welfare online PHP training,Help PHP learners grow quickly!