c# - 对 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

我是否在正确的轨道上首先重新安排层次结构中的节点？哪些类(class)对此有用(重新安排和 future 的过程)？ Graph 的子类？ 链表?

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

如果您正在搜索，那么您将插入您的比较代码，而不是“输出节点数据”，如果您想在找到第一个项目时退出，则可能会提前结束。