C#图遍历

Question

C#图遍历

12

这个算法在遍历图中的节点方面表现出色。

Dictionary<Node, bool> visited = new Dictionary<Node, bool>();

Queue<Node> worklist = new Queue<Node>();

visited.Add(this, false);

worklist.Enqueue(this);

while (worklist.Count != 0)
{
    Node node = worklist.Dequeue();

    foreach (Node neighbor in node.Neighbors)
    {
        if (!visited.ContainsKey(neighbor))
        {
            visited.Add(neighbor, false);
            worklist.Enqueue(neighbor);
        }
    }
}

我可以使用这个方法在图中找到目标节点。工作列表在处理过程中会出列（或弹出）项目。一旦我找到了目标，如何返回到节点的完整路径？

更新：我正在尝试找出如何反转到根路径。该方法在根节点上调用，之后子节点可能有两个父节点，因此不能简单地在每个节点上调用父属性并向上遍历。

该方法的目标是查找路径，而不是迭代所有节点或检查节点是否存在。

- blu

4个回答

0

“this”指的是当前实例，它是否是图的“根”，如果有这样的东西？

图是循环的还是非循环的？我不知道图论中所有术语。

这是我真正想知道的：

A -> B -> C ------> F
     B -> D -> E -> F

以下是我的问题：

这会发生吗？
你的代码中的“this”是否会从B开始？
F的路径将是什么？

如果图形在分裂时从未重新连接，不包含循环，并且“this”始终是图形的根/起点，则简单的字典将处理路径。

Dictionary<Node, Node> PreNodes = new Dictionary<Node, Node>();

对于每个访问的节点，将相邻节点作为键，它所属的邻居节点作为值添加。这将使您能够在找到目标节点后返回并获取反向路径。

换句话说，在完整遍历后，上述图形的字典将如下所示：

B: A
C: B
D: B
E: D
F: C (or E, or both?)

要找到E节点的路径，只需回溯：

E -> D -> B -> A

这会给你路径:

A -> B -> D -> E

- lassevk

0

由于您并没有始终跟踪“当前”节点的路径，因此在找到目标时必须构建该路径。如果您的Node类具有Parent属性，则可以轻松地向上回溯树以构建完整路径。

- Peter Lillevold

0

Peter几乎是正确的。我认为你不能在节点类中存储到父顶点的链接，因为它取决于您开始广度优先搜索的顶点。您需要创建一个父字典，其中键是节点，值是父节点。当您访问每个顶点（但在处理之前）时，将父项添加到字典中。然后，您可以沿着父路径向上走回根顶点。

- Jason Punyon

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Konrad Rudolph · Accepted Answer

跟踪前继节点。在最简单的实现中，这是一个字典，通常在伪代码中表示为π：

Dictionary<Node, bool> visited = new Dictionary<Node, bool>();
Dictionary<Node, Node> π = new Dictionary<Node, Node>();

Queue<Node> worklist = new Queue<Node>();

visited.Add(this, false);

worklist.Enqueue(this);

while (worklist.Count != 0)
{
    Node node = worklist.Dequeue();

    foreach (Node neighbor in node.Neighbors)
    {
        if (!visited.ContainsKey(neighbor))
        {
            visited.Add(neighbor, false);
            π.Add(neighbor, node);
            worklist.Enqueue(neighbor);
        }
    }
}

然后你可以遍历这些前驱节点，从任何节点（如e）开始回溯路径：

while (π[e] != null) {
    Console.WriteLine(e);
    e = π[e];
}