DFS 和 BFS 程序的有用 C# 类/方法

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 允许您对 XML 数据使用熟悉的 LINQ 方法。这就是我建议的，除非你有自定义要求需要显式使用 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作为堆栈，这应该可以满足您的目的。