Click here to Skip to main content
15,889,820 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
// Implementing BFS Algorithm
import java.util.ArrayList;  
import java.util.LinkedList;  
import java.util.Queue;  
  
public class BFS  
{   
    private Queue<Node> queue;                              // Queue that will contain some of Nodes
    static ArrayList<Node> nodes=new ArrayList<Node>();              
    static class Node  
    {  
        int data;                                           
        boolean visited;  
        Node(int data)  
        {  
            this.data=data;  
        }       
    }  
    public BFS()  
    {  
        queue = new LinkedList<Node>();                 // Initialization of Queue  
    }  
 // find neighbors of node using adjacency matrix  
 // if adjacency_list[i][j]==1, then nodes at index i and index j are connected  
    public ArrayList<Node> findNeighbours(int adjacency_list[][],Node x)  
    {  
        int nodeIndex=-1;  
        ArrayList<Node> neighbours=new ArrayList<Node>();  
        for (int i = 0; i < nodes.size(); i++) 
        {  
            if(nodes.get(i).equals(x))  
            {  
                nodeIndex=i;  
                break;  
            }  
        }   
        if(nodeIndex!=-1)  
        {       
            for (int j = 0; j < adjacency_list[nodeIndex].length; j++) 
            {  
                if(adjacency_list[nodeIndex][j]==1)  
                {  
                    neighbours.add(nodes.get(j));  
                }  
            }  
        }  
        return neighbours;  
    }   
    //Push Node in the Queue then remove it [FIFO]
    //Get Neighbours from the brevious function findNeighbours and add to Queue Nodes that only not visited
    //Printing Nodes Visited at each step and The Number of Vertex visited at each step
    public  void bfs(int adjacency_list[][], Node node)  
    {  
        queue.add(node);  
        node.visited=true;  
        while (!queue.isEmpty())  
        {   
            Node element=queue.remove();  
            System.out.print("\n    " + element.data + "\t\t ");  
            ArrayList<Node> neighbours=findNeighbours(adjacency_list,element);  
            int C=0; // Count 
            for (int i = 0; i < neighbours.size(); i++) {  
            Node n=neighbours.get(i); 
            if(n!=null && !n.visited)  
            {  
                C++; 
                System.out.print(n.data + " "); 
                queue.add(n);  
                n.visited=true;  
            }   
        }  
        System.out.print("\t\t\t\t" + C);
        }  
    }   
    public static void main(String arg[])  
    {   
        //Graph that you want Doing BFS on it
        //Adding Nodes
        Node node1 =new Node(1);  
        Node node2 =new Node(2);  
        Node node3 =new Node(3);  
        Node node4 =new Node(4);  
        Node node5 =new Node(5);  
        Node node6 =new Node(6);  
        Node node7 =new Node(7); 
        Node node8 =new Node(8);   
        nodes.add(node1);  
        nodes.add(node2);  
        nodes.add(node3);  
        nodes.add(node4);  
        nodes.add(node5);  
        nodes.add(node6);  
        nodes.add(node7);
        nodes.add(node8); 
        //AdjacencyList that compines adjacencyMatrix with edge lists
        int adjacency_list[][] = {  
        {0,1,1,0,0,0,0,0},  // Node 1: 1  
        {1,0,1,1,1,0,0,0},  // Node 2 :2  
        {1,1,0,0,1,0,1,1},  // Node 3: 3  
        {0,1,0,0,1,0,0,0},  // Node 4: 4  
        {0,1,1,1,0,1,0,0},  // Node 5: 5  
        {0,0,0,0,1,0,0,0},  // Node 6: 6  
        {0,0,1,0,0,0,0,1},  // Node 7: 7
        {0,0,1,0,0,0,1,0},  // Node 8: 8 
        };  
        System.out.println("The BFS traversal of This Graph is :- "); 
        System.out.print("Traversal       Visited       Number of Vertex visited at each step");  
        BFS bfsExample = new BFS();  
        bfsExample.bfs(adjacency_list, node1);   //Calling to bfs function with root vertex 
        System.out.println();
    }  
}  


What I have tried:

I want convert adjacency matrix to adjanceny list in this BFS code, thanks :)
Posted
Comments
Richard MacCutchan 4-Feb-17 8:56am    
What is the problem?

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900