查找未知（树状）数据结构中一个节点范围内的所有节点

有一天，我做了一个快速工具，以确定问题的确切含义，但是有一个固定的范围，只需使用一个愚蠢的数量for循环，但我想使它在可用的可用范围内工作。查找未知（树状）数据结构中一个节点范围内的所有节点

像

this

在外观的数据结构凡你按照正确的道路（这往往会打破我的实现每个节点都可以链接到节点的任何其他号码，都可以链接到它自身）。

这只是定义为

type Node struct { Name string ID int }

，你可以得到它使用返回节点一片后者从一个数据库约5000项信息的方法连接节点的列表。

最初我尝试了一些与递归有关的东西，这些东西刚刚结束时，我的头部和代码都受到了伤害，结果无法工作。我似乎无法理解这一点。

在此先感谢，如果这种类型的数据具有特定的名称，我很想知道它是什么！

来源

2014-10-12 THUNDERGROOVE

这是一个众所周知的图形问题。先查找“广度搜索”http://en.wikipedia.org/wiki/Breadth-first_search和“深度搜索优先”http://en.wikipedia.org/wiki/Depth-first_search。两者都可以通过递归或迭代来解决，但递归很容易实现。 – siritinga 2014-10-12 07:26:43

这绝对能让我朝着正确的方向发展，并且它的运行速度与我的静态实现相同。 – THUNDERGROOVE 2014-10-12 08:16:40

我的最终代码看起来是这样的

func rec(x Node, depth int) Node { 
    s := make([]Node, 0) 
    if depth == 0 { 
     s = append(s, x) 
    } else { 
     for _, y := range x.Get() { 
      s = append(s, rec(y, depth-1)...) 
     } 
    } 
    return s 
}

，它表现的很出色。感谢siritinga为我指出正确的方向。

来源

2014-10-12 08:20:47 THUNDERGROOVE

如果图中存在循环，这不会创建无限循环吗？如果需要确保不会发生，可以添加重复过滤器。 – 2014-10-12 09:23:08

是的，通常你有一个属性“visited”，最初设置为false。当你访问一个节点时，你将访问设置为true。这样你就不会遵循任何循环。 – siritinga 2014-10-12 11:08:25

欢迎您！顺便说一下，我想'rec'会返回'[] Node'而不是'Node'，不是吗？ – siritinga 2014-10-12 11:11:35

查找未知（树状）数据结构中一个节点范围内的所有节点

回答

相关问题