# DFS - Depth First Search using C, Java, Python Programming Language

## 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
};

// DFS algo
void DFS(struct Graph* graph, int vertex) {

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->visited[i] = 0;
}
return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
// Add edge from src to dest
struct node* newNode = createNode(dest);

// Add edge from dest to src
newNode = createNode(src);
}

// Print the graph
void printGraph(struct Graph* graph) {
int v;
for (v = 0; v < graph->numVertices; 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);

printGraph(graph);

DFS(graph, 2);

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

Output

cmd
2 -> 1 ->

2 -> 0 ->

3 -> 1 -> 0 ->

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 boolean visited[];

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

for (int i = 0; i < vertices; i++)
}

void addEdge(int src, int dest) {
}

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

while (ite.hasNext()) {
}
}

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

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

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

Output

cmd
Following is Depth First Traversal
2 3

## Demonstration

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