c++ - 广度优先搜索输入

Question

我不确定如何处理为广度优先搜索作业提供的输入。我们假设遍历一个图并输出遍历的顺序。这是有向边的列表:

0 1
0 2
2 6
6 1
7 9
4 0
6 4
6 3
9 3
6 2
8 6
1 4
5 6
1 2
6 5
2 3
2 7
5 7
9 0

遍历:0 1 2 4 6 3 7 9 5

我不确定如何正确遍历它？一旦到达节点 1 和 2，我如何才能到达列表中更靠后的其他节点 1 和 2？

我知道我必须使用单独的列表(这是一个单独的问题)来跟踪节点，但是最好先订购 list 吗？

并不是真正地寻找代码只是一个起点，但如果您想用代码示例来回答，我必须使用 C++ 中的循环链表。

Answer 1

如果要用BFS遍历，需要用到队列结构:例如:

• 获取第一个节点 (0)。
• 将 (0) 个节点放入队列。

• 重复这个过程，直到队列不为空。

  1. 出列 (0)
  2. 如果尚未访问，则检查节点 (0) 的子节点
     1. 根据您的输入 ("0 1") 边意味着它唯一的 child 是 1 所以将 1 放入队列。
  3. 打印(即 0)。

  结束循环结束

换句话说。下一次迭代将是 1 有两个 child ，即 1 (2) 和 1 (4) 将所有 child 放入队列并出队 1 并打印。下一次迭代将是，使 2 出队，有三个 child ，即 2 (6)、2 (3) 和 2 (7 ) 将所有 child 放入队列并打印2。下一次迭代将使 4 出队，只有一个 child ，即 4 (0) 但您已经打印并访问了 0 所以只需打印 < strong>4.

你可以使用这个queue结构。对于输入，您可以使用链接列表、数组或结构。