## What is Depth First Search

DFS or Depth First Search is a way to traverse a tree. The stack data-structure is used in this Depth First Search (DFS).

The edges that leads to an unvisited node are called discovery edges while the edges that leads to an already visited node are called block edges.

Pseudo Code Algorithm:

``````n ← number of nodes
Initialize visited[ ] to false (0)
for(i=0;i<n;i++)
visited[i] = 0;

void DFS(vertex i) [DFS starting from i]
{
visited[i]=1;
for each w adjacent to i
if(!visited[w])
DFS(w);
}``````

## Code Examples

### #1 Depth First Search Using Array in C Programming

```Code - C Programming```

Copy The Code &

Input

cmd
Enter number of vertices: 8
0 1 1 1 1 0 0 0
1 0 0 0 0 1 0 0
0 1 1 1 1 0 0 0
0 1 1 1 1 0 0 0
0 1 1 1 1 0 0 0
0 1 1 1 1 0 0 0
0 1 1 1 1 0 0 0
0 1 1 1 1 0 0 0

Output

cmd
0
1
5
2
3
4

### #2 DFS Problem solution using Graph in C Programming

```Code - C Programming```

``````#include <stdio.>
#include <stdlib.h>

struct node {
int vertex;
struct node* next;
};

struct node* createNode(int v);

struct Graph {
int numVertices;
int* visited;

// We need int** to store a two dimensional array.
// Similary, we need struct node** to store an array of Linked lists
struct node** adjLists;
};

// DFS algo
void DFS(struct Graph* graph, int vertex) {
struct node* adjList = graph->adjLists[vertex];
struct node* temp = adjList;

graph->visited[vertex] = 1;
printf("Visited %d \n", vertex);

while (temp != NULL) {
int connectedVertex = temp->vertex;

if (graph->visited[connectedVertex] == 0) {
DFS(graph, connectedVertex);
}
temp = temp->next;
}
}

// Create a node
struct node* createNode(int v) {
struct node* newNode = malloc(sizeof(struct node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}

// Create graph
struct Graph* createGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;

graph->adjLists = malloc(vertices * sizeof(struct node*));

graph->visited = malloc(vertices * sizeof(int));

int i;
for (i = 0; i  <  vertices; i++) {
graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}
return graph;
}

// Add edge
void addEdge(struct Graph* graph, int src, int dest) {
// Add edge from src to dest
struct node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;

// Add edge from dest to src
newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}

// Print the graph
void printGraph(struct Graph* graph) {
int v;
for (v = 0; v  <  graph->numVertices; v++) {
struct node* temp = graph->adjLists[v];
printf("\n Adjacency list of vertex %d\n ", v);
while (temp) {
printf("%d -> ", temp->vertex);
temp = temp->next;
}
printf("\n");
}
}

int main() {
struct Graph* graph = createGraph(4);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 2, 3);

printGraph(graph);

DFS(graph, 2);

return 0;
}
``````
Copy The Code &

Output

cmd
Adjacency list of vertex 0
2 -> 1 ->

Adjacency list of vertex 1
2 -> 0 ->

Adjacency list of vertex 2
3 -> 1 -> 0 ->

Adjacency list of vertex 3
2 ->
Visited 2
Visited 3
Visited 1
Visited 0

### #3 DFS Code Example with Java Programming

```Code - Java Programming```

``````import java.util.*;

class Graph {
private LinkedList < Integer> adjLists[];
private boolean visited[];

// Graph creation
Graph(int vertices) {
adjLists = new LinkedList[vertices];
visited = new boolean[vertices];

for (int i = 0; i  <  vertices; i++)
adjLists[i] = new LinkedList();
}

// Add edges
void addEdge(int src, int dest) {
adjLists[src].add(dest);
}

// DFS algorithm
void DFS(int vertex) {
visited[vertex] = true;
System.out.print(vertex + " ");

Iterator < Integer> ite = adjLists[vertex].listIterator();
while (ite.hasNext()) {
int adj = ite.next();
if (!visited[adj])
DFS(adj);
}
}

public static void main(String args[]) {
Graph g = new Graph(4);

g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 3);

System.out.println("Following is Depth First Traversal");

g.DFS(2);
}
}``````
Copy The Code &

Output

cmd
Following is Depth First Traversal
2 3
Advertisements

## Demonstration

DFS - Breadth First Search using C, Java, Python Programming Language