5
\$\begingroup\$

I was asked to implement a graph and BFS and DFS.

Please comment. Is it understandable? Is my algorithm correct? Are there any optimizations?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication2
{
    public class Graph
    {
        public List<Node> list;
        public Graph()
        {
            list = new List<Node>();
        }
    }

    public class Node
    {
        public int Index { get; set; }
        public List<Node> neighbors;
        public Node(int index)
        {
            Index = index;
            neighbors = new List<Node>();
        }
        public void AddNeighbor(int index)
        {
            neighbors.Add(new Node(index));
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication2
{
    public class BFS
    {
        public BFS()
        {
              Graph graph = new Graph();
              graph.list.Add(new Node(0));
              graph.list.ElementAt<Node>(0).AddNeighbor(1);
              graph.list.ElementAt<Node>(0).AddNeighbor(2);
              graph.list.ElementAt<Node>(0).neighbors.ElementAt<Node>(0).AddNeighbor(3);
              GraphTraverseBFS(graph);
        }
        public void GraphTraverseBFS(Graph graph)
        {
            Queue<Node> queue = new Queue<Node>();
            queue.Enqueue(graph.list[0]);
            while(queue.Count > 0)
            {
                Node tempNode = queue.Dequeue();
                Console.WriteLine("Node number: " +tempNode.Index);
                foreach (var item in tempNode.neighbors)
                {
                    queue.Enqueue(item);
                }
            }
        }
    }    
}



using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication2
{
    public class DFS
    {

        public Graph graph { get; set; }
        public DFS()
        {
              graph = new Graph();

              graph.list.Add(new Node(0));
              graph.list.ElementAt<Node>(0).AddNeighbor(1);
              graph.list.ElementAt<Node>(0).AddNeighbor(2);
              graph.list.ElementAt<Node>(0).neighbors.ElementAt<Node>(0).AddNeighbor(3);
              GraphTraverseDFS(graph);
        }

        public void GraphTraverseDFS(Graph graph)
        {
            Stack<Node> stack = new Stack<Node>();
            stack.Push(graph.list[0]);
            while (stack.Count != 0)
            {
                Node tempNode = stack.Pop();
                Console.WriteLine("Node number: " + tempNode.Index);
                var negibours = tempNode.neighbors;
                foreach (var item in negibours)
                {
                    stack.Push(item);
                }
            }
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ shouldn't a graph have a parent and children instead of neighbours? \$\endgroup\$ – dfhwze Jun 24 at 19:43
6
\$\begingroup\$

Let's take a step back and consider the API.

Suppose I want to test the BFS traversal on different graphs.

To call GraphTraverseBFS I need to first create a BFS object. But the BFS constructor creates its own graph and runs GraphTraverseBFS on that. There is no clean way for me to just test it on my own graph.

So let's say that's fixed. Now I want to write some unit tests for GraphTraverseBFS. I can't currently do this without redirecting where the output messages are written to, and then parsing the output. This is more work than I want to do. Ideally I would be able to write something like

CollectionAssert.AreEqual(new[] { 0, 1, 2, 3 }, BFS.Traverse(graph));

The same comments hold for DFS.


List<T> is (generally) an implementation detail.

Graph has a public field List<Node> list. The fact that you're storing nodes in a List is an implementation detail, and should not be exposed to users of this code.

  • The user now has full access to the methods of List, and can manipulate the list however they want. This is more power than they should have.

  • The user can reassign the field, e.g. graph.list = null.

  • It locks you in to your choice of graph representation, as the user may write code that depends on list being a List.

Similar comments hold for Node.neighbors.

One pattern I like for letting the user iterate over a collection, without exposing the choice of implementation is to

  • Have a private readonly field with your choice of collection type (List, HashSet, etc)

  • Have a public IEnumerable<T> read-only property that exposes the collection for iteration

In code, it looks like this

public class Graph
{
    private readonly List<Node> nodes = new List<Node>();

    public IEnumerable<Node> Nodes
    {
        get { return this.nodes; }
    }

    ...
}

This might not be entirely suitable for you needs, but this is the sort of API I would suggest

public class Graph
{
    // Creates a new graph with `count` vertices.
    public Graph(int count)

    public IEnumerable<int> GetNeighbors(int node);

    public void AddEdge(int n, int m);
}

public static class BFS
{
    public static IEnumerable<int> Traverse(Graph graph, int startNode = 0);
}

public static class DFS
{
    public static IEnumerable<int> Traverse(Graph graph, int startNode = 0);
}
\$\endgroup\$
2
\$\begingroup\$

You should store a 'visited' property on a graph, because if you do not, you can end up in an infinite loop since some nodes may point back to a node they came from. In both your implementations, you would add this 'new node' back onto you queue or stack, respectively, and search them again. Therefore, if your code has no way to not visit a node twice, you may end up in an infinite loop.

\$\endgroup\$
0
\$\begingroup\$

Only one advise, you should keep the visited Node list as well in one collection.

\$\endgroup\$
  • 2
    \$\begingroup\$ Can you expand on why you believe this would be an improvement? \$\endgroup\$ – forsvarir Apr 15 '17 at 8:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.