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

Algorithm


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 & Try With Live Editor

Input

x
+
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

x
+
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 & Try With Live Editor

Output

x
+
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 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 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 & Try With Live Editor

Output

x
+
cmd
Following is Depth First Traversal
2 3

Demonstration


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