java - 显示在java中执行了BFS遍历的图的树结构

Question

我在研究广度优先搜索或 BFS 算法时遇到了一个想法。我显示了我在其中实现了 BFS 的图的树结构。现在也许我可以使用链表以不同的方式显示树结构，但我想修改我用来显示树结构的 BFS 方法

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++;
        }
    }
}

上面给出的是我的 BFS 方法，有人可以帮助我让我知道我必须对代码进行哪些确切的修改才能获得所需的输出

例如，假设给定的邻接矩阵是这样的:

 {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}

这个图的树结构是这样的

     A

   /   \

  B     F

      /   \

     E     G

        /   |   \

       C    H     D

Answer 1

可以使用 BFS 执行您描述的操作，但很麻烦。后序遍历或中序遍历可能更合适。检查here看看什么合适。