 # Depth First Search (DFS) – Graph Traversal

• Definition
• Conceptual Implementation
• Java Code & Explanation
• Applications of DFS

Definition

Depth First Search (DFS) is an algorithm for traversing Graph Data Structure. The algorithm starts at some arbitrary node in the graph and explores as far as possible along each branch before backtracking.

Stack Data structure is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking the graph.

Conceptual Implementation Java Code & Explanation

```

import java.util.*;

class Main{

public static class Graph{

int vertices; // Number of vertices

// Constructor of the Graph

Graph(int v){

vertices = v;

adj  = new LinkedList[v]; // Initialization of the array with size of vertices

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

}

}

// Make Edge between u and v vertices

}

/*

First mark the sourceNode as visited

Print the Node

Iterate through all its neighbor until all the node marked as visited

*/

void DFS(int sourceNode, boolean[] visited){

visited[sourceNode] = true;

System.out.print(sourceNode + " ");

while(iterator.hasNext()){

int neighbourToSourceNode = iterator.next();

DFS(neighbourToSourceNode, visited);

}

}

// Util Method

void DFSUtil(int sourceNode){

boolean visited[] = new boolean[vertices]; // Array to store marked visited vertices

DFS(sourceNode, visited); // Call DFS Method

}

}

public static void main(String[] args) {

Graph graph = new Graph(7);

extracted(graph);

}

private static void extracted(Graph graph) {

graph.DFSUtil(0);

}

}```

Output Applications

• Topological Sorting
• Scheduling Problem
• Cycle detection in graph
• Maze Problem
• Sudoku Puzzle