2
\$\begingroup\$

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>();
        }
    }
}
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Great answer just want to add that property with no setter is behaving as a readonly field and this is a C# 6 feature. \$\endgroup\$ – Denis Jan 21 '17 at 16:13

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.