Обход графа C #

Этот алгоритм отлично справляется с обходом узлов в графе.

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 на каждом узле и вернуться назад.

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


c# graph traversal
person blu    schedule 05.03.2009    source источник

Ответы (4)


arrow_upward
11
arrow_downward

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

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];
}
person Konrad Rudolph    schedule 05.03.2009
comment
у вас есть π.Add (сосед, был в гостях); а значение словаря π - это узел, что вы отслеживаете в значении? - person blu; 05.03.2009
comment
Предшественник. Словарь здесь фактически действует как функция: для входного значения n укажите узел-предшественник. Вход - это ключ, возвращаемое значение - это значение. - person Konrad Rudolph; 05.03.2009
comment
Разве это не было бы π.Add (neighbour, node) ;? Концепция звучит хорошо, но код недействителен, я просто думаю, что это опечатка. - person blu; 05.03.2009
comment
Хорошо, это работает, изменяя π.Add (сосед, посещенный); в π.Add (сосед, узел) ;. Это не работает, когда целью является корень, но я добавил для этого специальную обработку. В целом это правильное решение, только не полное. Спасибо. - person blu; 05.03.2009
comment
Привет, синь, извини, я не проводил тестирования заранее, потому что у меня не было вашего графического API, поэтому я просто набрал код как есть. Ваше исправление, конечно, необходимо. - person Konrad Rudolph; 05.03.2009

arrow_upward
0
arrow_downward

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

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

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

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
person Lasse V. Karlsen    schedule 05.03.2009

arrow_upward
0
arrow_downward

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

person Peter Lillevold    schedule 05.03.2009

arrow_upward
0
arrow_downward

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

person Jason Punyon    schedule 05.03.2009