对 DFS 和 BFS 程序有用的 C# class/methods

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 映射这些节点，并打印节点的状态 mapped/retrieved。

示例提示：

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

结果是：

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，但我的理解是你在"tree"中尽可能走得远，然后只有当当前节点没有更多节点可以遍历时才返回到前一个节点。在此过程中不应丢失任何节点。

回答：我可能只是将 LinkedList 用作堆栈，这应该可以很好地满足您的目的。

Answer 2

不过，根据您的具体要求，您可能不需要为遍历编写任何自定义代码。 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);
        }
    }
}

如果您正在搜索，那么您将插入比较代码而不是 "output node data"，如果您想在找到第一个项目时退出，则可能会提前退出。

对 DFS 和 BFS 程序有用的 C# class/methods

Useful C# class/methods for DFS and BFS program

c#

data-structures

collections

depth-first-search

breadth-first-search