Objective – Given a graph, do the depth first traversal(DFS).
What is depth-first traversal– Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking. Source – Wiki
Example:
Approach:
- Use Stack.
- First add the Starting Node to the Stack.
- Pop out an element from Stack and add all of its connected nodes to stack.
- Repeat the above two steps until the Stack is empty.
- Below is a walk through of the graph above.
Complete Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.LinkedList; | |
import java.util.Stack; | |
public class Graph { | |
int vertex; | |
LinkedList<Integer> list[]; | |
public Graph(int vertex) { | |
this.vertex = vertex; | |
list = new LinkedList[vertex]; | |
for (int i = 0; i <vertex ; i++) { | |
list[i] = new LinkedList<>(); | |
} | |
} | |
public void addEdge(int source, int destination){ | |
//add forward edge | |
list[source].addFirst(destination); | |
} | |
public void DFS(){ | |
System.out.print("Depth First Traversal: "); | |
boolean[] visited = new boolean[vertex]; | |
Stack<Integer> stack = new Stack<Integer>(); | |
for(int startIndex=0; startIndex<vertex; startIndex++){ | |
if(visited[startIndex]==false) { | |
stack.push(startIndex); | |
visited[startIndex] = true; | |
while (stack.isEmpty() == false) { | |
int nodeIndex = stack.pop(); | |
System.out.print(nodeIndex + " "); | |
LinkedList<Integer> nodeList = list[nodeIndex]; | |
for (int i = 0; i < nodeList.size(); i++) { | |
int dest = nodeList.get(i); | |
if (visited[dest] == false) { | |
stack.push(dest); | |
visited[dest] = true; | |
} | |
} | |
} | |
} | |
} | |
System.out.println(); | |
} | |
public void printGraph(){ | |
for (int i = 0; i <vertex ; i++) { | |
LinkedList<Integer> nodeList = list[i]; | |
if(nodeList.isEmpty()==false) { | |
System.out.print("source = " + i + " is connected to nodes: "); | |
for (int j = 0; j < nodeList.size(); j++) { | |
System.out.print(" " + nodeList.get(j)); | |
} | |
} | |
System.out.println(); | |
} | |
} | |
public static void main(String[] args) { | |
Graph graph = new Graph(6); | |
graph.addEdge(0, 1); | |
graph.addEdge(0, 2); | |
graph.addEdge(1, 2); | |
graph.addEdge(1, 3); | |
graph.addEdge(3, 4); | |
graph.addEdge(2, 3); | |
graph.addEdge(4, 0); | |
graph.addEdge(4, 1); | |
graph.addEdge(4, 5); | |
graph.printGraph(); | |
graph.DFS(); | |
} | |
} | |
Output:
source = 0 is connected to nodes: 2 1 source = 1 is connected to nodes: 3 2 source = 2 is connected to nodes: 3 source = 3 is connected to nodes: 4 source = 4 is connected to nodes: 5 1 0 Depth First Traversal: 0 1 3 4 5 2