C# 图遍历

Question

该算法在遍历图中的节点方面做得很好。

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

我可以用它来查找图中的目标节点。处理工作列表时，工作列表会将项目出列（或弹出）。一旦找到目标，如何返回节点的完整路径？

更新我正在尝试找出如何反转到根的路径。该方法是在根节点上调用的，之后子节点可能有两个父节点，所以并不像在每个节点上调用parent属性并向上遍历那么简单。

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

Answer 1

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

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

Answer 2

我尝试使用这个片段来获取替代路径从顶点（我的代码中的顶点），使用源和命运，但只是不工作...

public String EncontrarMenorCaminho(Vertice o, Vertice d)
        {
            Dictionary<Vertice, bool> visited = new Dictionary<Vertice, bool>();
            Dictionary<Vertice, Vertice> previous = new Dictionary<Vertice, Vertice>();
            Queue<Vertice> worklist = new Queue<Vertice>();
            String operacao = "Registro de operações realizadas:\r\n\r\n";

            visited.Add(o, false);
            worklist.Enqueue(o);
            while (worklist.Count != 0)
            {
                Vertice v = worklist.Dequeue();
                foreach (Vertice neighbor in EncontrarVizinhos(v))
                {
                    if (!visited.ContainsKey(neighbor))
                    {
                        visited.Add(neighbor, false);
                        previous.Add(neighbor, v);
                        worklist.Enqueue(neighbor);
                    }
                }
            }

            if (previous.Count > 0)
            {
                for (int p = 0; p < previous.Count; p++)
                {
                    Vertice v1 = previous.ElementAt(p).Key;
                    Vertice v2 = previous.ElementAt(p).Value;
                    EncontrarAresta(v1, v2).Selecionado = true;
                    EncontrarAresta(v2, v1).Selecionado = true;
                    operacao += v1.Info.ToString() + "x" + v2.Info.ToString() + "\r\n";
                }
            }

            List<Vertice> grupos = new List<Vertice>();

            foreach (Aresta a in ArestasSelecionadas())
            {
                if (!grupos.Contains(a.Origem)) grupos.Add(a.Origem);
            }

            foreach (Vertice v in grupos)
            {
                int menorpeso = this.infinito;
                foreach(Vertice vz in EncontrarVizinhos(v))
                {
                    Aresta tmp = EncontrarAresta(v,vz);
                    if (tmp.Selecionado == true && tmp.Peso < menorpeso)
                    {
                        menorpeso = tmp.Peso;
                    }
                    else
                    {
                        tmp.Selecionado = false;
                    }
                }

            }




            DesenharMapa();

            return operacao;

基本上操作是获得所有标记的边缘（Selecionado = true）并再次验证是否有必要继续选择......

在这个例子中，我希望得到从椎骨'N'到顶点'Q'的最短路径：

在此处查看预览图片：

Answer 3

“这个”，即当前实例，图的“根”，是否有这样的东西？

该图是有环图还是无环图？恐怕我不知道图论的所有术语。

这就是我真正想知道的：

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

Answer 4

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

Answer 5

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