用于节点搜索的图遍历

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]

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

Answer 1

如果您有(或可以添加)回到父母的链接,您可以在第一次遇到节点时列出所有父母,然后在重复访问时跳过它.您有多个选项可以跟踪是否已访问过某个节点:

1. 维护一组受访节点并检查当前节点是否在该集合中.如果没有,处理它并将其添加到集合中; 否则跳过.

   优点:一般方法

   缺点:如果图表很大,可能会占用大量内存来维护集合

2. isVisited向节点添加成员值(false默认设置为)并在遇到节点时进行检查:如果值为false,则处理节点并设置isVisited为true; 否则跳过.

   优点:减少额外内存

   缺点:侵入性,任务特定,额外变量即使在不需要时也存在,对于需要同时执行多个此类"已经处理"决策的任务而言不能很好地扩展

如果父链接选项不可用,则可以在额外的映射中维护子到父关系:在处理节点时,从子映射到父集.完成初始处理(构建映射)后,迭代映射并列出每个节点及其父节点.

直接父链接的优点是在构建/修改图形时没有额外的维护(除非您希望保持映射是最新的)

的缺点是,你必须要处理经过一系列的修改,以图形的结构图中每个时间重新建立映射(除非-见adventage的说明)

注意:如果图中有定向(父对子)圆,则遍历所有子项遍历常规图可能会导致无限循环.我想你的问题并非如此,只是为了涵盖所有基础:你可以在处理图形时维护一组"访问过的"节点.对可用选项的讨论与第一部分("链接回父母")部分的讨论相同