Полезные классы / методы C# для программ DFS и BFS

Question

У меня есть XML-файл узлов с их соединениями. Что-то вроде:

<Graph>
  <Node Name = "A">
    <ConnectsTo>B</ConnectsTo>
    <ConnectsTo>H</ConnectsTo>
  </Node>
  <Node Name="B"></Node>
  <Node Name="C">
    <ConnectsTo>E</ConnectsTo>
  </Node>
  <Node Name="D">
    <ConnectsTo>C</ConnectsTo>
  </Node>
  <Node Name="E"></Node>
  <Node Name="F">
    <ConnectsTo>D</ConnectsTo>
    <ConnectsTo>G</ConnectsTo>
  </Node>
  <Node Name="G">
    <ConnectsTo>E</ConnectsTo>
    <ConnectsTo>I</ConnectsTo>
  </Node>
  <Node name="H">
    <ConnectsTo>C</ConnectsTo>
    <ConnectsTo>J</ConnectsTo>
    <ConnectsTo>G</ConnectsTo>
  </Node>
  <Node name="I">
    <ConnectsTo>E</ConnectsTo>
  </Node>
  <Node name="J">
    <ConnectsTo>A</ConnectsTo>
  </Node>
</Graph>

Теперь я сопоставлю эти узлы с использованием BFS или DFS и напишу, как узлы отображаются / извлекаются.

Пример подсказки:

Choose (1)DFS (2)BFS : 1
Choose Starting Vertex : A

Result : 

A B
A H J
A H C E
A H G E
A H G I E

Я на правильном пути реорганизации первых узлов в иерархии? Какие классы будут полезны для этого (перестановка и будущий процесс)? Подкласс Graph? LinkedList?

Answer 1

Однако, в зависимости от ваших конкретных требований, вам может не потребоваться писать какой-либо специальный код для обхода. LINQ to XML позволяет вам использовать знакомые методы LINQ с данными XML. Это то, что я бы порекомендовал, если у вас нет пользовательских требований, требующих явного использования DFS или BFS.

Если вам нужно сделать DFS или BFS, это довольно просто. Насколько мне известно, нет никаких встроенных методов, которые позволили бы вам сделать один или другой. Но их не сложно написать. Стандартные структуры данных - это все, что вам нужно. Обход в глубину обычно выполняется с помощью рекурсии:

void Dfs(NodeType node)
{
    foreach (var child in node.Children)
    {
        Dfs(child);
    }
    // here, output node information
}

Самый простой способ сделать обход в ширину - с помощью очереди:

void Bfs(NodeType node)
{
    var theQueue = new Queue<NodeType>();
    theQueue.Enqueue(node);
    while (theQueue.Count > 0)
    {
        var n = theQueue.Dequeue();
        // output node data
        // then add each child to the queue
        foreach (var child in n.Children)
        {
            theQueue.Enqueue(child);
        }
    }
}

Если вы ищете, то вместо "данных выходного узла" вы вставите свой код сравнения и, возможно, рано, если захотите выйти с первым найденным элементом.

Answer 2

Будет ли результат для:

Choose (1)DFS (2)BFS : 1
Choose Starting Vertex : A

Result :

не быть

A B
A B H
A B H J
A B H J C
A B H J C E
A B H J C E G
A B H J C E G I

??? может быть, я уже забыл, как делать DFS, но, насколько я понимаю, вы заходите в "дерево" как можно дальше, а затем возвращаетесь к предыдущему узлу только тогда, когда для текущего узла больше нет узлов, которые нужно пройти. Ни один узел не должен быть потерян в процессе.

Ответ: Я бы, вероятно, просто использовал LinkedList в качестве стека, и это должно служить вашим целям.