BFS - Breadth First Search
DFS - Depth First Search
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/**
*
*/
/**
* @author sachin.srivastava
* @tek9g.blogspot.com
* @github.com/sks1130/
*
*/
public class Graph_BFS_DFS {
private static int numberOfNodes;
private static int[][] adjMatrix;
private static boolean[] visited;
public static void main(String[] args) {
numberOfNodes = 9 ;
adjMatrix = new int[numberOfNodes][numberOfNodes];
visited = new boolean[numberOfNodes];
adjMatrix = new int[][]{ { 0, 1, 0, 1, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0, 0, 0, 1, 0 },
{ 0, 0, 0, 1, 0, 1, 0, 1, 0 },
{ 1, 0, 1, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 1 },
{ 0, 0, 1, 0, 0, 0, 1, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 1, 1, 0, 0, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 1, 0, 0, 0, 0 } };
for (int i = 0; i < numberOfNodes; i++) {
System.out.println(Arrays.toString(adjMatrix[i]));
}
BFS(0);
DFS(0);
}
public static void BFS(int root){
if(root >= numberOfNodes){
System.out.println("input node is beyond range");
return;
}
System.out.println("---BFS--------");
Queue<Integer> queue = new LinkedList<>();
queue.add(root);
visited[root] = true;
System.out.println("visited node-->" + root + " ");
while(queue.size()!=0){
int head = queue.remove();
int child = -1;
while((child=getUnvisitedNode(head))!=-1){
queue.add(child);
visited[child] = true;
System.out.println("visited node-->" + child + " ");
}
}
clearAllVisitedNodes();
}
public static void DFS(int root){
if(root >= numberOfNodes){
System.out.println("input node is beyond range");
return;
}
System.out.println("---DFS--------");
Stack<Integer> stack = new Stack<>();
stack.push(root);
visited[root] = true;
System.out.println("visited node-->" + root + " ");
while(!stack.isEmpty()){
int head = stack.peek();
int child = -1;
if(( child = getUnvisitedNode(head))!=-1){
stack.push(child);
visited[child] = true;
System.out.println("visited node-->" + child + " ");
} else {
stack.pop();
}
}
clearAllVisitedNodes();
}
public static void clearAllVisitedNodes(){
for (int i = 0; i < visited.length; i++) {
visited[i] = false;
}
}
public static int getUnvisitedNode(int n ){
for (int i = 0; i < adjMatrix[n].length; i++) {
if( adjMatrix[n][i] == 1 && !visited[i]){
return i;
}
}
return -1;
}
}
Output :
[0, 1, 0, 1, 0, 0, 0, 0, 1]
[1, 0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 1, 0, 1, 0]
[1, 0, 1, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0, 0]
[0, 1, 1, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 1, 0, 0, 0, 0]
---BFS--------
visited node-->0
visited node-->1
visited node-->3
visited node-->8
visited node-->7
visited node-->2
visited node-->4
visited node-->5
visited node-->6
---DFS--------
visited node-->0
visited node-->1
visited node-->7
visited node-->2
visited node-->3
visited node-->4
visited node-->8
visited node-->5
visited node-->6
Enjoy the coding!!!!
