Click here to Skip to main content
14,665,452 members
Rate this:
Please Sign up or sign in to vote.
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, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100