节点搜索的图遍历

Question

在下面的图表中，子部分被递归遍历。每个子部分必须报告其直接父级。问题是子[3]必须同时在同一行报告其两个直接父级（即子[2]和子[4]）。

traverse(Node node)
{
    if(node == null)
        return;

    for(Node child : node.getChilds()) {
        traverse(child);
    }
}

Parent 
|---child[1]
|       child[2]
|           child[3]
|---child[4]
        child[3]

目前，我正在逐个节点遍历图形，并生成以下输出 -

Node      Immediate Parent
--------------------------
child[2]  child[1]
child[3]  child[2]
child[3]  child[4]

期望的输出是 -

Node      Immediate Parent
--------------------------
child[2]  child[1]
child[3]  child[2], child[4]

什么是搜索节点并为图形生成期望输出的最佳方法？任何帮助都将不胜感激。

- user32262

---

在您提供的第一个示例中存在一个循环，因此它不是一棵树，而是一个图。 - betabandido

@betabandido 实际上，我认为他所描述的图是一个有向无环图。 - skynet

你的节点实际结构是什么？哪些限制条件会决定哪种搜索方法最好？ - Samuel Edwin Ward

Answer 1

如果您有（或可以添加）一个指向父节点的链接，您可以在第一次遇到节点时列出所有父节点，然后在重复访问时跳过它。您有多种选项来跟踪节点是否已被访问：

1. 维护一个已访问节点的集合并检查当前节点是否在集合中。如果不在，则处理它并将其添加到集合中；否则跳过。

优点：通用方法

缺点：如果图形很大，维护集合可能需要大量内存

2. 向节点添加一个isVisited成员值（默认设置为false），并在遇到节点时进行检查：如果值为false，则处理该节点并将isVisited设置为true；否则跳过。

优点：较少的附加内存

缺点：侵入性、任务特定、即使不需要额外的变量也存在，对于需要同时进行多个“已处理”决策的任务来说，不具有良好的可扩展性。

如果没有父链接选项，您可以在额外的映射中维护子-父关系：在处理节点时，将子节点映射到其父节点集合。完成初始处理（构建映射）后，迭代映射并列出每个节点及其父节点。

与直接父链接相比，优点是在构建/修改图形时没有额外的维护（除非您也想保持映射最新）。

缺点是每次在修改图形结构后想要处理图形时都必须重新构建映射（除非——见优点的注释）。

注意：通过遍历所有子节点来遍历一般图形，如果图形中存在有向（父到子）圆圈，则可能导致无限循环。我想这不是您问题的情况，但只是为了覆盖所有基础：您可以在处理图形时维护一个“已访问”节点集合。可用选项的讨论与第一部分（“指向父节点的链接”）中的讨论相同。

- Attila