javaalgorithmtreebreadth-first-searchtree-structure

Showing the tree structure of a graph in which BFS traversal has been performed in java


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

Solution

  • 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.