current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 2 down vote favorite

Please comment on my DFS implementation and test, I would like to get comments about algorithm correctness.

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking. 

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace JobInterviewTests
{
    [TestClass]
    public class DFSUnitTest
    {
        [TestMethod]
        public void CheckCorrectOrder()
        {
            GraphNode root = new GraphNode("A");
            root.Neighbors.Add(new GraphNode("F"));
            root.Neighbors.Add(new GraphNode("E"));
            var temp = new GraphNode("B");
            var temp2 = new GraphNode("C");
            var temp3 = new GraphNode("D");
            temp2.Neighbors.Add(temp3);
            temp.Neighbors.Add(temp2);
            root.Neighbors.Add(temp);

            List<string> result =TraverseDFS(root);
            Assert.AreEqual("A",result[0]);
            Assert.AreEqual("B",result[1]);
            Assert.AreEqual("C",result[2]);
            Assert.AreEqual("D",result[3]);
            Assert.AreEqual("E",result[4]);
            Assert.AreEqual("F",result[5]);
        }

        private List<string> TraverseDFS(GraphNode root)
        {
            if (root == null)
            {
                return null;
            }

            List<string> result = new List<string>();
            Stack<GraphNode> s = new Stack<GraphNode>();
            s.Push(root);
            while (s.Any())
            {
                GraphNode curr = s.Pop();
                result.Add(curr.Value);
                foreach (var node in curr.Neighbors)
                {
                    s.Push(node);
                }
            }
            return result;
        }
    }

    public class GraphNode
    {
        public string Value { get; set; }
        public List<GraphNode> Neighbors { get; set; }

        public GraphNode(string s)
        {
            Value = s;
            Neighbors = new List<GraphNode>();
        }
    }
}
share|improve this question
up vote 4 down vote accepted

The implementation of depth-first traversal is correct. But there are several elements of this program and tests that could be improved.

Prefer empty collections over null values

When the input graph is empty, it would be better to return an empty list instead of null. Collections are used for iterating over its elements. When a collection variable can be null, that's troublesome, because before you can iterate over it, you have to check that it's not null.

Constraints and limitations

The implementation will only work with directed graphs without cycles, otherwise you will have an infinite loop. This is important to include in the description. A common follow-up question at an interview is how to make it work in graphs with cycles.

Weak tests

The test knows too much about the implementation. There are 6 possible valid depth-first traversals of the example graph, and the test knows exactly which one to expect. It all comes down to the evaluation order of neighbor, in your implementation it's the reverse order that they were added. Either this implementation should be documented, or the test should not depend on it.

The example graph is not a good choice to demonstrate depth-first traversal, because A F E B C D would be valid both as depth-first and as breadth-first traversal. A more expressive example would be:

    A
   / \
  B   C
 /     \
D       E

With this example all depth-first and breadth-first traversals would be distinct.

Lastly, a technical detail, instead of comparing the elements of a list one by one to values, you could compare entire lists, which would be a lot easier to type.

List<string> expected = new List<string>(new string[] { "A", "B", "C", "D", "E", "F" });
List<string> result = TraverseDFS(root);
Assert.AreEqual(expected, result);

Don't provide setters if you don't really need

The fields of GraphNode are never modified, therefore the setters are unnecessary.

share|improve this answer
    
thank you very much i appreciate the feedback very much – Gilad 2 days ago
    
Great answer just want to add that property with no setter is behaving as a readonly field and this is a C# 6 feature. – denis 2 days ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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