在 Go 中遍历孩子的谱系

Question

我有一个庞大的人口谱系 ( map[int][]int)，其中关键是动物，而价值切片中的父母 (两个)。没有父母的动物将有父母的负整数。

其次，我有一个动物列表，我想建立它们的特定谱系并写入文件。我列表谱系中的所有动物都应该写入同一个文件。

pedigree := map[int][]int{

    1:  []int{2, 3},

    2:  []int{-1, 5},

    3:  []int{6, 7},

    4:  []int{8, 9},

    5:  []int{-1, -2},

    6:  []int{8, -2},

    7:  []int{-1, -2},

    8:  []int{-1, -2},

    9:  []int{10, -2},

    10: []int{-1, 4}

}

list := []int{1, 4}

以及我对 io.Writer 编写的文件的期望：

  1   2   3

  2  -1   5

  3   6   7

  5  -1  -2

  6   8  -2

  7  -1  -2

  8  -1  -2

  4   8   9

  9  10  -2

 10  -1   4

所以我需要一个递归函数来遍历从基础动物开始的谱系，然后在所有路径上继续，直到达到负数的父母。

更重要的是，我列表中的动物被确定为导致谱系周期的动物（动物 4 成为其自身的伟大父母）。

我已经使用以下代码进行了尝试：

type tree struct {

    sire   *tree

    dam    *tree

    animal int

    base   int

    path   []int

}

func newTree(a, s, d, b int) tree {

    return tree{

        animal: a,

        sire:   &tree{animal: s, base: b},

        dam:    &tree{animal: d, base: b},

        base:   b,

    }

}

for _, animal := range list {

    myTree = newTree(animal, pedigree[animal][0], pedigree[animal][1], 0)

    walk(myTree, written, fw) // written is a map of integers and fw is io.Writer

}

func walk(t tree, written map[int]int, writer io.Writer) tree {

    style := "%12d%12d%12d\n"

    if t.animal == t.base {

        return t

    }

    if t.base == 0 {  // for the first iteration

        t.base = t.animal

    }

    if _, ok := written[t.animal]; !ok {

        sire := t.sire.animal

        dam := t.dam.animal

        if sire == 0 {

            sire = t.base

        }

        if dam == 0 {

            dam = t.base

        }

        written[t.animal] = 0

        io.WriteString(writer, fmt.Sprintf(style, t.animal, sire, dam))

    }

    // Shift forward.

    if t.sire.animal > 0 {

        myTree := newTree(t.sire.animal, pedigree[t.sire.animal][0], pedigree[t.dam.animal][1], t.base)

        walk(myTree, written, writer)

    }

我的谱系由大约 1300 万只动物组成，但我无法让功能在正确的点停止并在stack overflow完成几只动物后感到恐慌。我相信我的一些问题是：

参与循环的动物是基础动物，所以我应该检查是否animal == base (1->2->3->1)

参与循环的动物不是基础动物(1->2->3->4->5->6->3)

任何帮助将不胜感激。

Answer 1

由于您的系谱图中可以有循环，因此您可能会陷入这样的循环。这意味着您必须检测循环并停止在那里构建。你可以通过稍微改变你的树来做到这一点。首先，您tree按值传递对象，但附加指向它的指针。将指针传递给周围的树：func walk(t *tree, written map[int]int, writer io.Writer) *tree {}更好的方法可能是：func (t *tree) walk(written map[int]int, writer io.Writer) {...}您还应该将 a 添加*parent到树中，以便检测循环：type tree struct {    parent *tree    sire   *tree    dam    *tree    animal int    base   int    path   []int}每次创建新关卡时，适当设置父级：myTree := newTree(t.sire.animal, pedigree[t.sire.animal][0], pedigree[t.dam.animal][1], t.base)myTree.parent=tmyTree.walk(written, writer)然后添加一个函数来测试你是否进入循环：func (t *tree) loop(animal int) bool {   for t!=nil {       if t.animal==animal {          return true       }       t=t.parent   }   return false}并检查您是否正在进入循环：if !myTree.loop(myTree.animal) {   myTree.walk(written, writer)}