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:

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

**Pseudo-code:**

Recursive:

1procedureDFS(G,v): 2 labelvas discovered 3for alledges fromvtowinG.adjacentEdges(v)do4ifvertexwis not labeled as discoveredthen5 recursively call DFS(G,w)

Non-recursive:

1procedureDFS-iterative(G,v): 2 letSbe a stack 3S.push(v) 4whileSis not empty 5v=S.pop() 6ifvis not labeled as discovered: 7 labelvas discovered 8for alledges fromvtowinG.adjacentEdges(v)do9S.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.**

**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 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/

[…] https://simpledevcode.wordpress.com […]

LikeLike