Graph

In this tutorial we are learning about Depth First Search algorithm.

The graph that we will consider can be both a directed graph and a non directed graph and can also contain cycles.

In DFS or Depth First Search we have to keep track of vertices that are visited in order to prevent revisiting them. For this we use an array to mark visited and unvisited vertices. In DFS we also take help of a STACK. When a vertex is visited, we push it into the stack. The process ends when the stack becomes empty.

We start the process by considering any one of the vertex as the starting vertex.

Consider the following graph.

There are 4 vertices in the graph so we will need an adjacency matrix having 4 rows and 4 columns.

Adj | 0 | 1 | 2 | 3 |

0 | ||||

1 | ||||

2 | ||||

3 |

Row and Column name is same as the vertex name. The cells of the adjacency matrix Adj will contain 1 if there is an edge from starting vertex to ending vertex. If there is no edge then it will contain 0.

As per the given graph our adjacency matrix will look like the following.

Adj | 0 | 1 | 2 | 3 |

0 | 0 | 1 | 0 | 0 |

1 | 0 | 1 | 1 | 1 |

2 | 1 | 0 | 0 | 1 |

3 | 0 | 0 | 1 | 0 |

To keep track of the visited vertices we will use the visited[] array. The size of this array will be equal to the number of vertices in the graph. In this case it is 4.

Initially, we will set all the elements in the array visited[] as 0 which means unvisited. As we progress we will be visiting new vertices so, we will be marking the respective index in the visited[] array with 1. Note, the vertices in the graph are names from 0 to 3 so, we can use the visited[] array index to represent the respective vertex.

We will also use a stack to push and pop vertices into and out of it as we progress.

Step 1: We consider a vertex as the starting vertex, in this case vertex 3.

Step 2: We push vertex 3 into the stack.

Step 3: We set visited[3] = 1 which means we have visited vertex 3.

Step 4: Print starting vertex 3 as the first result.

Step 5: If the stack is not empty then, take the top vertex in the stack. Else STOP.

Step 6: Set i = vertex at the top of the stack.

Step 7: If visited[j] == 0 AND Adj[i][j] == 1 where j = 0 to 3, then Next result is j

Step 8: Set visited[j] = 1.

Step 9: Push j into the stack. Go to step 5.

```
#include <stdio.h>
#define STACK_SIZE 20
#define MAX 20
void dfs(int Adj[][MAX], int n, int source);
int main(void) {
//Adj matrix
int Adj[][MAX] = {
{0,1,0,0},
{0,1,1,1},
{1,0,0,1},
{0,0,1,0}
};
int n = 4; //no. of vertex
int starting_vertex = 3;
dfs(Adj, n, starting_vertex);
return 0;
}
void dfs(int Adj[][MAX], int n, int source) {
//variables
int i, j;
bool change = false;
//visited array to flag the vertex that
//were visited
int visited[MAX];
//top of the stack
int tos = 0;
//stack
int stack[MAX];
//set visited for all vertex to 0 (means unvisited)
for(i = 0; i < MAX; i++) {
visited[i] = 0;
}
//mark the visited source
visited[source] = 1;
//push the vertex into stack
stack[tos] = source;
//print the vertex as result
printf("%d ", source);
//continue till stack is not empty
while(tos >= 0) {
//to check if any vertex was marked as visited
change = false;
//get vertex at the top of the stack
i = stack[tos];
for(j = 0; j < n; j++) {
if(visited[j] == 0 && Adj[i][j] == 1) {
//mark vertex as visited
visited[j] = 1;
//push vertex into stack
tos++;
stack[tos] = j;
//print the vertex as result
printf("%d ", j);
//vertex visited
change = true;
break;
}
}
if(change == false) {
tos--;
}
}
printf("\n");
}
```

Output: 3 2 0 1

The time complexity of Depth First Search (DFS) is O(V+E) where, V is the total number of vertices in the graph and E is the total number of edges in the graph.