In this post we'll see how to write a Java program for depth-first search (DFS) traversal of a graph.
Graph traversal
To traverse a graph, where you try to reach all the connected vertices from the starting vertex, can be done in following ways-
- Depth-first search (DFS)
- Breadth-first search (BFS)
Depth-First Search
DFS traversal tries to traverse all adjacent vertices from the start vertex, it tries to go deep while exploring a branch and backtracks to starting point once it reaches dead end to start exploring another branch.
For example, if we have the following graph and the starting vertex is "A".
From "A" you have to go to any vertex, adjacent to "A". So, you see there can be multiple DFS traversal orders of a graph based on how adjacent vertex is picked. Let's say in this case it goes to "B" then you need to visit the next adjacent vertex, which will be "F" and then "I". With this order ABFI the current branch reaches a dead end (you have explored the full depth of this branch) so you need to backtrack and then pick the next adjacent vertex from starting point "A" which is "C" and so on. Final DFS traversal order is A B F I C G D E H J.
DFS traversal for graph is similar to Binary tree DFS traversal with one difference, graph may have cycles so you need to keep track of visited vertices by having an extra array of all vertices and you mark the vertices which are already visited.
Depth-First Search Java program
Depth-First Search traversal program can be written using a recursive method or by using an iterative method with a stack to keep track of traversal.
Graph can be represented using adjacency matrix or by using adjacency list, which of these two ways is used to represent the graph has to be taken in account while writing Japa program for DFS traversal of the graph. Note that in this article undirected graph traversal is done.
Refer post Graph Adjacency Representation - Java Program to get better explanation of graph adjacency representation using adjacency matrix or adjacency list.
Process for DFS traversal is as given below-
For recursive logic
- Start from the starting vertex and mark it as visited.
- Recursively visit all the unvisited adjacent vertices. Mark the visited vertices.
- Backtrack when no unvisited adjacent vertices left.
For iterative logic
- Start from the starting vertex, mark it as visited and push it on the stack
- Visit an unvisited adjacent vertex. Mark the vertex as visited and push it on the stack
- Keep doing step 2 while there are adjacent vertices in that branch.
- When there are no unvisited adjacent vertices, backtrack by popping vertex of the stack and look for adjacent vertex in another branch.
Here is the complete Java program with both recursive and iterative methods when adjacency matrix is used to represent graph.
import java.util.Stack;
public class GraphBFS {
private int numOfVertices;
private int[][] adjMatrix;
// to store all the vertex labels
Vertex[] vertices;
private int temp = 0;
// Vertex class as nested class
static class Vertex{
String label;
// to track the visited vertices
boolean visited;
Vertex(String label){
this.label = label;
}
public String getLabel() {
return label;
}
public void setLabel(String label) {
this.label = label;
}
public boolean isVisited() {
return visited;
}
public void setVisited(boolean visited) {
this.visited = visited;
}
}
GraphBFS(int numOfVertices){
this.numOfVertices = numOfVertices;
vertices = new GraphBFS.Vertex[numOfVertices];
adjMatrix = new int[numOfVertices][numOfVertices];
}
//Method to add all the graph vertices
public void addVertex(String label) {
vertices[temp++] = new Vertex(label);
}
public void addEdge(int source, int destination) {
if((source < 0 || source > numOfVertices) || (destination < 0 || destination > numOfVertices)) {
System.out.println("Invalid edge addition");
return;
}
adjMatrix[source][destination] = 1;
// For undirected graph reverse setting also required
adjMatrix[destination][source] = 1;
}
public void printGraph() {
for(int i = 0; i < adjMatrix.length; i++) {
for(int j = 0; j < adjMatrix[0].length; j++) {
System.out.print(adjMatrix[i][j] + "\t");
}
System.out.println();
}
}
/* Recursive logic start */
public void dfs(int startVertex) {
System.out.println("DFS Traversal (Recursive): ");
dfsRecursive(startVertex, vertices);
}
public void dfsRecursive(int startVertex, Vertex[] vertices) {
vertices[startVertex].setVisited(true);
System.out.print(vertices[startVertex].getLabel() + " ");
for (int i = 0; i < numOfVertices; i++) {
if (adjMatrix[startVertex][i] == 1 && !vertices[i].isVisited()) {
dfsRecursive(i, vertices);
}
}
}
/* Recursive logic End */
/* Iterative logic Start */
public void dfsIterative(int startVertex) {
boolean[] visited = new boolean[numOfVertices];
Stack<Integer> stack = new Stack<Integer>();
stack.push(startVertex);
visited[startVertex] = true;
System.out.print(vertices[startVertex].getLabel() + " ");
while(!stack.isEmpty()) {
int v = getNextUnvisitedVertex(stack.peek(), visited);
if(v == -1) {
stack.pop();
}else {
visited[v] = true;
System.out.print(vertices[v].getLabel() + " ");
//System.out.println(v);
stack.push(v);
}
}
}
private int getNextUnvisitedVertex(int v, boolean[] visited) {
for(int i = 0; i < numOfVertices; i++) {
if(adjMatrix[v][i] == 1 && visited[i] == false) {
return i;
}
}
return -1;
}
/* Iterative logic End */
public static void main(String[] args) {
GraphBFS graph = new GraphBFS(10);
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addVertex("F");
graph.addVertex("G");
graph.addVertex("H");
graph.addVertex("I");
graph.addVertex("J");
graph.addEdge(0, 1); //A-B
graph.addEdge(0, 2); //A-C
graph.addEdge(0, 3); //A-D
graph.addEdge(0, 4); //A-E
graph.addEdge(1, 5); //B-F
graph.addEdge(5, 8); //F-I
graph.addEdge(2, 6); //C-G
graph.addEdge(4, 7); //E-H
graph.addEdge(7, 9); //H-J
//graph.printGraph();
graph.dfs(0);
System.out.println("");
System.out.println("Graph DFS Traversal (Iterative): ");
graph.dfsIterative(0);
}
}
Output
DFS Traversal (Recursive): A B F I C G D E H J Graph DFS Traversal (Iterative): A B F I C G D E H J
Important points about the program
- Uses a static inner class Vertex to encapsulate a vertex with fields as label to store the label of the vertex and Boolean field visited to keep track of the vertex which is already visited.
- Adjacency matrix is used here to represent a graph.
- Array named vertices is used to store the vertices of the graph and mark the vertices which are already visited.
- Method named dfsRecursive() shows the recursive logic.
- Method named dfsIterative () shows the iterative logic.
Here is the complete Java program with both recursive and iterative methods when adjacency list is used to represent graph.
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
public class GrapdhBFSAL {
private Map<String, List<String>> adjList;
// To keep track of already visited vertices
private Set<String> visited;
GrapdhBFSAL(){
adjList = new HashMap<>();
visited = new HashSet<String>();
}
public void addVertex(String v) {
adjList.putIfAbsent(v, new ArrayList<String>());
}
public void addEdge(String source, String destination) {
if(!adjList.containsKey(source)) {
addVertex(source);
}
if(!adjList.containsKey(destination)) {
addVertex(destination);
}
adjList.get(source).add(destination);
// Reverse link also required for undirected graph
adjList.get(destination).add(source);
}
// Method to display graph
public void printGraph() {
adjList.forEach((k, v) -> {
System.out.print("Vertex " + k+ " connects to ");
v.forEach(e -> System.out.print(e + " "));
System.out.println();
});
}
/* Recursive logic start */
public void dfs(String startVertex) {
System.out.println("DFS Traversal (Recursive): ");
dfsRecursive(startVertex);
}
public void dfsRecursive(String startVertex) {
visited.add(startVertex);
System.out.print(startVertex + " ");
for (String s : adjList.getOrDefault(startVertex, Collections.emptyList())) {
if (!visited.contains(s)) {
dfsRecursive(s);
}
}
}
/* Recursive logic end */
/* Iterative logic Start */
public void dfsIterative(String startVertex) {
Stack<String> stack = new Stack<String>();
stack.push(startVertex);
visited.add(startVertex);
System.out.print(startVertex + " ");
while(!stack.isEmpty()) {
String v = getNextUnvisitedVertex(stack.peek());
if(v.isBlank()) {
stack.pop();
}else {
visited.add(v);
System.out.print(v + " ");
stack.push(v);
}
}
}
private String getNextUnvisitedVertex(String v) {
for (String s : adjList.getOrDefault(v, Collections.emptyList())) {
if (!visited.contains(s)) {
return s;
}
}
return "";
}
/* Iterative logic End */
public static void main(String[] args) {
GrapdhBFSAL graph = new GrapdhBFSAL();
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("A", "D");
graph.addEdge("A", "E");
graph.addEdge("B", "F");
graph.addEdge("F", "I");
graph.addEdge("C", "G");
graph.addEdge("E", "H");
graph.addEdge("H", "J");
graph.printGraph();
// Uncomment this to run recursive method
//System.out.println("Graph DFS Traversal (Recursive): ");
//graph.dfs("A");
System.out.println("Graph DFS Traversal (Iterative): ");
graph.dfsIterative("A");
}
}
Output
Vertex A connects to B C D E Vertex B connects to A F Vertex C connects to A G Vertex D connects to A Vertex E connects to A H Vertex F connects to B I Vertex G connects to C Vertex H connects to E J Vertex I connects to F Vertex J connects to H Graph DFS Traversal (Iterative): A B F I C G D E H J
Important points about the program
- In the Java program, Map and List collections are used to represent adjacency list.
- A HashSet named visited is used to store the vertices of the graph and mark the vertices which are already visited.
- Method named dfsRecursive() shows the recursive logic.
- Method named dfsIterative () shows the iterative logic.
Time and space complexity of DFS graph traversal
If total number of vertices in the graph are V and the total number of edges are E then the time complexity is O(V2) when graph is represented as an adjacency matrix.
In adjacency matrix we have a 2D array of VXV which means while checking for neighbours of any vertex we have to scan the whole row which is O(V) meaning O(V2) for V vertices. This scanning has to be done for V vertices which again is O(V) resulting in total time complexity of O(V + V2) which can be considered O(V2).
With adjacency list, only adjacent vertices are stored as a list for each vertex. For each vertex, the algorithm iterates over adjacency list of that vertex. In an adjacency list representation, every edge appears exactly once (directed graph) or twice (undirected graph).
Since the total time = time for vertex processing + time for scanning adjacency list for each vertex = O(V) + O(E) So, the time complexity is O(V + E).
Auxiliary space requirement is O(V) to store visited vertices in an array or set. In recursive method, call stack may go up to the recursive depth of V in worst case so recursive call space requirement is O(V).
For iterative method, stack may also end up storing V vertices (in worst case) so the space requirement is O(V) for stack used in iterative method. Thus, the total space requirement is O(V) + O(V), discarding the constants the space complexity is O(V).
That's all for this topic Java Program - Depth First Search (DFS) Traversal For Graph. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Advanced Tutorial Page
Related Topics
You may also like-
No comments:
Post a Comment