Depth First Search (DFS) in a Graph

Depth first search is an algorithm which searches or traverses all the vertices in a graph. It starts to traverse the graph based on a start vertex. The algorithm traverses the vertices in depth.

As graphs can have cycles we should not visit any visited vertex twice. For this purpose the algorithm must know if a vertex is visited and it shouldn’t visit it again. To implement the algorithm usually a helper stack is used. Let’s have a look at an example to better understand how the algorithm works.

Let’s say that we have the simple graph above and we want to traverse the graph by starting from vertex A.

At this point we have traversed all the vertices in the graph, so the DFS algorithm finishes.

Implementation

Lets first create a simple vertex class which will represent the vertices in a graph.

    public class Vertex
    {
        public Vertex(string name)
        {
            this.Name = name;
        }

        public string Name { get; set; }

        public bool IsVisited { get; set; }
    }

Next let’s create a graph class that will implement DFS algorithm.

    public class Graph
    {
        // Adjacency list which will keep the connections between vertices
        private readonly Dictionary<Vertex, List<Vertex>> adjLists;

        public Graph()
        {
            adjLists = new Dictionary<Vertex, List<Vertex>>();
        }

        // Add edge between src---->dest vertices
        public void AddEdge(Vertex src, Vertex dest)
        {
            if (this.adjLists.ContainsKey(src))
            {
                this.adjLists[src].Add(dest);
            }
            else
            {
                this.adjLists.Add(src, new List<Vertex> { dest });
            }
        }

        // Applying DFS algorithm and returning a list of traversed vertices 
        public List<Vertex> Dfs(Vertex source)
        {
            List<Vertex> result = new List<Vertex>();

            Stack<Vertex> vertexStack = new Stack<Vertex>();

            vertexStack.Push(source);

            while (vertexStack.Count > 0)
            {
                var vertex = vertexStack.Pop();
                vertex.IsVisited = true;
                result.Add(vertex);

                // Add all unvisited adjacency 
                //vertices of currently visited vertex
                // into the stack
                foreach (var v in this.adjLists[vertex])
                {
                    if (!v.IsVisited)
                    {
                        vertexStack.Push(v);
                    }
                }
            }

            return result;
        }
    }

Finally we will construct the graph from the example above and run the DFS algorithm on it to show the order in which the vertices will be visited.

        static void Main(string[] args)
        {
            var graph = new Graph();

            var vA = new Vertex("A");
            var vB = new Vertex("B");
            var vC = new Vertex("C");
            var vD = new Vertex("D");
            var vE = new Vertex("E");

            graph.AddEdge(vA, vB);
            graph.AddEdge(vA, vC);
            graph.AddEdge(vA, vD);

            graph.AddEdge(vB, vA);

            graph.AddEdge(vC, vA);
            graph.AddEdge(vC, vE);

            graph.AddEdge(vD, vA);

            graph.AddEdge(vE, vC);

            var traversed = graph.Dfs(vA);

            foreach (var t in traversed)
            {
                Console.Write($"{t.Name} ");
            }
        }

When we run the console app the result will be:

A D C E B

The time complexity of the DFS algorithm is O(V + E), where V is the number of vertices and E is the number of edges.