Graphs - Breadth first search in java

in #bfs7 years ago

Code can be forked from https://github.com/sks1130/Algos/blob/master/src/main/java/Graph_BFS_DFS.java

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

*/
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);
}
public static void BFS(int root){
    if(root >= numberOfNodes){
        System.out.println("input node is beyond range");
    }
    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 + " ");
        }
    }

}

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]
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