import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class BFS
{
private Queue<Node> queue;
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>();
}
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;
}
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;
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[])
{
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);
int adjacency_list[][] = {
{0,1,1,0,0,0,0,0},
{1,0,1,1,1,0,0,0},
{1,1,0,0,1,0,1,1},
{0,1,0,0,1,0,0,0},
{0,1,1,1,0,1,0,0},
{0,0,0,0,1,0,0,0},
{0,0,1,0,0,0,0,1},
{0,0,1,0,0,0,1,0},
};
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);
System.out.println();
}
}
What I have tried:
I want convert adjacency matrix to adjanceny list in this BFS code, thanks :)