# 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.

### Implementation (C#)

```//an implementation of an adjacency list, I will do a recursive method
class GraphList
{
class Edge
{
public Edge next;
}
class Graph
{
public bool visited;
public string description;
}
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++)
{
{
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[w].visited)//if the next edge  isnt visited
{
dfsRecursive(w);//recurse on w
}
}
{
Console.WriteLine();
EdgeNode current = null;
EdgeNode nextInList = null;
for(int i = 1; i < graphSize; i++)
{
if (current.next != null)
{
nextInList = current.next;
}

while (current != null && nextInList != null)
{
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();