cari

Rumah  >  Soal Jawab  >  teks badan

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

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

思路???

大家讲道理大家讲道理2803 hari yang lalu632

membalas semua(3)saya akan balas

  • 巴扎黑

    巴扎黑2017-04-17 13:17:17

    提示:用广度优先算法(基本可以保证生成的树有minimum radius)

    基本上就是广度优先遍历这张图,然后把遍历过的节点放到树上,并且标记下来,下次不要再访问遍历过的节点。可以考虑用个链表来储存访问过的节点。

    balas
    0
  • 阿神

    阿神2017-04-17 13:17:17

    可以先阅读wikipedia上关于BFS和DFS的解释以及相关的实现。

    从根节点开始,每次找到最近的且没有访问过的节点。下次从所有这些节点开始,继续重复上述过程。

    最小生成树也可以参考MST的相关算法,prim,kruskal(不知道有没有拼写错误)。

    经典问题多看看,这种相类似的问题就会迎刃而解。

    balas
    0
  • 天蓬老师

    天蓬老师2017-04-17 13:17:17

    BFS跑一遍不就是一个最小半径生成树了么?
    使用邻接表存图吧.vector<int>g[SIZE].
    还有最小生成树(一般指的是value最小)

    balas
    0
  • Batalbalas