Java Program for Depth First Search or DFS for a Graph
Depth First Traversal (or DFS) for a graph is similar to Depth First Traversal of a tree.
Prerequisite: Graph knowledge is important to understand the concept of DFS.
What is DFS?
DFS or Depth First Traversal is the traversing algorithm. DFS can be used to approach the elements of a Graph. To avoid processing a node more than once, use a boolean visited array. A graph can have more than one DFS traversal.
Example:
Input: N = 4, E = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3Output: DFS from vertex 1: 1 2 0 3
Working of DFS
Depth-first search is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
Java Program for Depth First Search for a Graph
Below is the implementation of the above approach:
// Java program to print DFS traversal
// from a given graph
import java.io.*;
import java.util.*;
// This class represents a
// directed graph using adjacency
// list representation
class Graph {
private int V;
// Array of lists for
// Adjacency List Representation
private LinkedList<Integer> adj[];
// Constructor
@SuppressWarnings("unchecked") Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
// Function to add an edge into the graph
void addEdge(int v, int w)
{
// Add w to v's list.
adj[v].add(w);
}
// A function used by DFS
void DFSUtil(int v, boolean visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
System.out.print(v + " ");
// Recur for all the vertices adjacent to this
// vertex
Iterator<Integer> i = adj[v].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n])
DFSUtil(n, visited);
}
}
// The function to do DFS traversal.
// It uses recursive DFSUtil()
void DFS(int v)
{
// Mark all the vertices as
// not visited(set as
// false by default in java)
boolean visited[] = new boolean[V];
// Call the recursive helper
// function to print DFS
// traversal
DFSUtil(v, visited);
}
// Driver Code
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, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
System.out.println(
"Following is Depth First Traversal "
+ "(starting from vertex 2)");
// Function call
g.DFS(2);
}
}
Output
Following is Depth First Traversal (starting from vertex 2): 2 0 1 3
Complexity of the program above:
Time Complexity: O(V+E) where V is the number of vertices in the graph and E is the number of edges.
Auxiliary Space: O(V+E)
Please refer complete article on Depth First Search or DFS for a Graph for more details.