84669 personnes étudient
152542 personnes étudient
20005 personnes étudient
5487 personnes étudient
7821 personnes étudient
359900 personnes étudient
3350 personnes étudient
180660 personnes étudient
48569 personnes étudient
18603 personnes étudient
40936 personnes étudient
1549 personnes étudient
1183 personnes étudient
32909 personnes étudient
原题: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)
思路???
光阴似箭催人老,日月如移越少年。
提示:用广度优先算法(基本可以保证生成的树有minimum radius)
基本上就是广度优先遍历这张图,然后把遍历过的节点放到树上,并且标记下来,下次不要再访问遍历过的节点。可以考虑用个链表来储存访问过的节点。
可以先阅读wikipedia上关于BFS和DFS的解释以及相关的实现。
从根节点开始,每次找到最近的且没有访问过的节点。下次从所有这些节点开始,继续重复上述过程。
最小生成树也可以参考MST的相关算法,prim,kruskal(不知道有没有拼写错误)。
经典问题多看看,这种相类似的问题就会迎刃而解。
BFS跑一遍不就是一个最小半径生成树了么?使用邻接表存图吧.vector<int>g[SIZE].还有最小生成树(一般指的是value最小)
提示:用广度优先算法(基本可以保证生成的树有minimum radius)
基本上就是广度优先遍历这张图,然后把遍历过的节点放到树上,并且标记下来,下次不要再访问遍历过的节点。可以考虑用个链表来储存访问过的节点。
可以先阅读wikipedia上关于BFS和DFS的解释以及相关的实现。
从根节点开始,每次找到最近的且没有访问过的节点。下次从所有这些节点开始,继续重复上述过程。
最小生成树也可以参考MST的相关算法,prim,kruskal(不知道有没有拼写错误)。
经典问题多看看,这种相类似的问题就会迎刃而解。
BFS跑一遍不就是一个最小半径生成树了么?
使用邻接表存图吧.vector<int>g[SIZE].
还有最小生成树(一般指的是value最小)