I was studying about the Breadth First Search or BFS algorithm and I came across an idea . I display the tree structure of the graph in which I have implemented BFS. Now maybe I can just show the tree structure in a different way using linked lists, but I want to modify the BFS method that I am using to display the tree structure
public class BFS
{
private Queue<Integer> queue;
public BFS()
{
queue = new LinkedList<Integer>();
}
public void bfs(int adjacency_matrix[][], int source)
{
int number_of_nodes = adjacency_matrix[source].length - 1;
int[] visited = new int[number_of_nodes + 1];
int i, element;
visited[source] = 1;
queue.add(source);
while (!queue.isEmpty())
{
element = queue.remove();
i = element;
System.out.print(i + "\t");
while (i <= number_of_nodes)
{
if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
{
queue.add(i);
visited[i] = 1;
}
i++;
}
}
}
Given above is my BFS method , can someone help me into letting me know what exact modifications I have to make to the code so that I get the desired output
For example let's say the given adjacency matrix is like this:
{0,1,0,0,0,1,0,0
1,0,0,0,0,0,0,0
0,0,0,0,0,0,1,0
0,0,0,0,0,0,1,1
0,0,0,0,0,1,0,0
1,0,0,0,1,0,1,0
0,0,1,0,0,1,0,1
0,0,0,1,0,0,0,1}
The tree structure of this graph would be like this
A
/ \
B F
/ \
E G
/ | \
C H D
It's possible to do what you describe with BFS, but it's cumbersome. Post-Order Traversal or In-Order Traversal might be more appropriate. Check here and see what fits.