Обход графика 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);
        }
    }
}

Я могу использовать это, чтобы найти целевой узел на графике. Рабочий список удаляет (или выдает) элементы по мере их обработки. Как только я найду цель, как я могу вернуть полный путь к узлу?

Обновление Я пытаюсь выяснить, как изменить путь к корню. Метод вызывается на корневом узле, после этого у потомков может быть два родителя, поэтому это не так просто, как вызвать родительское свойство на каждом узле и вернуться обратно.

Цель метода - найти путь, а не перебирать все узлы или проверить, существует ли узел.

Answer 1

Отслеживание узлов-предшественников. В простейшей реализации это словарь, обычно обозначаемый как π в псевдокодах:

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

Питер почти прав. Я не думаю, что вы можете сохранить ссылку на родительскую вершину в классе узла, потому что она меняется в зависимости от вершины, с которой вы начинаете поиск в ширину. Вам необходимо создать родительский словарь, в котором ключами являются узлы, а значениями являются родительские узлы. Когда вы посещаете каждую вершину (но перед обработкой), вы добавляете родителей в словарь. Затем вы можете пройти по родительскому пути обратно к корневой вершине.

Answer 4

Поскольку вы не отслеживаете путь к «текущему» узлу все время, вам придется создать его, когда вы найдете цель. Если ваш класс Node имеет свойство Parent, вы можете легко вернуться к дереву, чтобы построить полный путь.

Answer 5

Является ли "это", то есть текущий экземпляр, "корнем" графа, если такое существует?

Является ли график циклическим или ациклическим? Боюсь, я не знаю всех терминов теории графов.

Вот что мне действительно интересно:

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

Вот мои вопросы:

• Это произойдет?
• Может ли "это" в вашем коде когда-либо начинаться с 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