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);
        }
    }
}

我可以使用它在图中找到目标节点。工作清单在处理工作清单时使项目出队（或弹出）。找到目标后，如何返回节点的完整路径？

更新 我试图弄清楚如何将路径反转到根目录。该方法在根节点上调用，之后子节点可能有两个父节点，所以并不像在每个节点上调用父属性并向上遍历那么简单。

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

4

4 回答 4

11

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

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];
}
于 2009-03-05T15:31:59.723 回答
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
于 2009-03-05T15:20:03.483 回答
0

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

于 2009-03-05T15:23:21.353 回答
0

Peter is almost correct. I don't think you can store a link to the parent vertex in the node class, because it changes depending on the vertex at which you start your breadth first search. You need to create a Parent Dictionary with the keys being nodes and the values being parent nodes. As you visit each vertex (but before processing) you add the parents to the dictionary. Then you can walk up the parent path back to the root vertex.

于 2009-03-05T15:36:36.280 回答