Graphs: Depth First Traversal (C#)


Continuing where we left off with Graphs, we saw that Dijkstra’s Shortest Path was an example of a breadth first search traversal. In this tutorial, we will implement a depth first traversal (also called DFS, depth first search).

What is depth first searching?

The whole idea of DFS algorithm is to go as far as possible from the given starting node searching for a target. In case we get to a node that has no successors, we get back (typically this is done recursively) and we continue with the last vertex that isn’t visited yet.

So basically we have 3 steps:

  1. Pick up a vertex that isn’t visited yet and mark it visited
  2. Go to its first non-visited successor and mark it visited
  3. If all the successors of the vertex are already visited or it doesn’t have successors – go back to its parent

Pseudo-code:

Recursive:

1  procedure DFS(G,v):
2      label v as discovered
3      for all edges from v to w in G.adjacentEdges(v) do
4          if vertex w is not labeled as discovered then
5              recursively call DFS(G,w)

Non-recursive:

1  procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5            v = S.pop() 
6            if v is not labeled as discovered:
7                label v as discovered
8                for all edges from v to w in G.adjacentEdges(v) do
9                    S.push(w)

Whats the difference between BFS and DFS?

  • BFS uses the adjacency matrix to represent a graph, while DFS (usually) uses an adjacency list (although both can work for either algorithm).
  • BFS starts at some source vertex and looks at the next successive vertices, and repeats the process for the next nodes. Think about BFS as waves in other words.
  • DFS starts at some source vertex and target vertex, finds a path between them. We can use DFS also to walk through all the vertices of a graph, in case the graph is connected.
  • Order of traversal is different as well, because BFS lists by level, and DFS lists by depth (for each level).
  • In short: BFS would visit the nodes in the order loosely resembling how far are they from the starting vertex. DFS would completely finish one branch before starting another one.
DFS vs BFS

DFS vs BFS

Adjacency List of a graph using DFS

Adjacency List of a graph using DFS

Implementation (C#)

//an implementation of an adjacency list, I will do a recursive method
    class GraphList
    {
        class Edge
        {
            public int adjGraphNode;
            public Edge next;
        }
        class Graph
        {
            public bool visited;
            public string description;
            public Edge head;
        }
        Graph[] adjList; //our main array
        int graphSize;
        public GraphList(){}//default ctor
        public void initGraph(string textFile)
        {
            //assume we've read in contents from a text file
            //and our graph is initialized
        }
        //DFS function starts here, a public method that goes through all the indices of the list
        //and calls a recursive dfs function if some node hasnt been visited yet
        public void dfs()
        {
            Console.WriteLine("***********DFS Output***********");
            Console.Write("Order: ");
            for (int v = 1; v < graphSize; v++)
            {
                if (!adjList[v].visited)
                {
                    dfsRecursive(v);
                }
            }
            Console.WriteLine();
        }
        //main dfs recursive implementation
        //takes a vertex, and performs dfs recursively
        private void dfsRecursive(int vertex)
        {
            adjList[vertex].visited = true;//mark v as visited
            Console.Write("{0} ", vertex);//do something with v, like print
            int w = vertex;//set w to the current vertex
            Edge n = null;
            if (adjList[vertex].head.next != null)
            {
                n = adjList[vertex].head.next;//get the next edge
                w = n.adjGraphNode;
            }
            if (!adjList[w].visited)//if the next edge (w) isnt visited
            {
                dfsRecursive(w);//recurse on w
            }
        }
        //displays the adjacency list
        public void displayAdjList()
        {
            Console.WriteLine();
            Console.WriteLine("***********Adjacency List***********");
            EdgeNode current = null;
            EdgeNode nextInList = null;
            for(int i = 1; i < graphSize; i++)
            {
                current = adjList[i].head;
                if (current.next != null)
                {
                    nextInList = current.next;
                }
                Console.WriteLine("Node: {0}, Description:{1}", current.adjGraphNode, adjList[i].description);

                while (current != null && nextInList != null)
                {
                    Console.Write(current.adjGraphNode);
                    while (nextInList != null)
                    {
                        string line = "->" + nextInList.adjGraphNode;
                        Console.Write(line);
                        nextInList = nextInList.next;
                    }
                }
                Console.WriteLine();
            }
        }
        //inserts an edge into the list
        private void insertEdge(int fromNode, int toNode)
        {
            Edge n = new Edge();
            n.adjGraphNode = toNode;
            n.next = null;
            n.next = adjList[fromNode].head.next;
            adjList[fromNode].head.next = n;
        }
    }

Bellman-Ford Algorithm

The only other graph traversal algorithm I did not cover is called the Bellman-Ford algorithm which has the ability to work with negative weighted edges. Much like Dijkstra’s shortest path, it is also used to find the shortest available path on graphs that have negative edge costs. I found a good tutorial with explanation here for this: https://compprog.wordpress.com/2007/11/29/one-source-shortest-path-the-bellman-ford-algorithm/

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s