Useful C # class / methods for DFS and BFS program

I have an XML file of nodes with their connections. Something like:

<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>

      

I will now map these nodes using BFS or DFS and print how the nodes are displayed / retrieved.

Example request:

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

      

Am I on the right track to reinstall nodes in the hierarchy? What classes would be helpful for this (rebuilding and future process)? Subclass Graph

? LinkedList

?

+3


source to share


2 answers


However, depending on your specific requirements, you may not need to write any custom bypass code. LINQ to XML allows you to use familiar LINQ techniques with XML data. This is what I would recommend unless you have custom requirements that explicitly require DFS or BFS to be used.

If you have to do DFS or BFS, it's pretty easy. As far as I know, there are no built-in methods that allow you to do this or that. But it's not hard to write them. Standard data structures are all you need. Traversing the first level is usually done recursively:

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

      



The easiest way to do width traversal is with a queue:

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

      

If you are looking then instead of "output node data" you should insert the comparison code and possibly early if you want to exit the first found element.

+1


source


Will there be a result for:

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

Result :

      

not to be



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

      

??? maybe I already forgot how to do DFS, but I figured you go as far into the "tree" as possible and then go back to the previous node when there are no more nodes to traverse for the current node.No nodes should be lost in the process ...

Answer: I would probably just use a LinkedList as a stack and that should serve your purposes just fine.

0


source







All Articles