0

我正在研究广度优先搜索或 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
4

1 回答 1

1

用 BFS 可以做你描述的事情，但是很麻烦。后序遍历或中序遍历可能更合适。检查这里，看看什么合适。

于 2017-06-20T01:39:36.500 回答