图遍历算法：广度优先搜索算法

本文概述

• 广度优先搜索（BFS）算法
• 算法
• 解

在本教程的这一部分中, 我们将讨论可用于遍历图形所有顶点的技术。

遍历图意味着检查图的所有节点和顶点。通过两种标准方法, 我们可以遍历图形。让我们详细讨论其中的每一个。

• 广度优先搜索
• 深度优先搜索

广度优先搜索（BFS）算法

广度优先搜索是一种图遍历算法, 该算法开始从根节点遍历图并探索所有相邻节点。然后, 它选择最近的节点并浏览所有未探索的节点。该算法对每个最近的节点遵循相同的过程, 直到找到目标为止。

广度优先搜索的算法如下。该算法开始于检查节点A及其所有邻居。在下一步中, 将探索A的最近节点的邻居, 然后继续执行其他步骤。该算法探索所有节点的所有邻居, 并确保每个节点仅被访问一次且没有节点被访问两次。

算法

• 步骤1：G中每个节点的SET STATUS = 1（就绪状态）
• 步骤2：使起始节点A入队并设置其STATUS = 2（等待状态）
• 步骤3：重复步骤4和5, 直到QUEUE为空
• 步骤4：使节点N出队。对其进行处理并设置其STATUS = 3（处理状态）。
• 步骤5：将所有处于就绪状态（状态STATUS = 1）的N邻居入队, 并将其状态STATUS = 2（等待状态）设置为[END OF LOOP]
• 步骤6：退出

例

考虑下图所示的图G, 计算从节点A到节点E的最小路径p。假定每个边的长度为1。

解

最小路径P可以通过应用广度优先搜索算法找到, 该算法将在节点A处开始并在E处结束。该算法使用两个队列, 即QUEUE1和QUEUE2。 QUEUE1保留所有要处理的节点, 而QUEUE2保留所有要处理并从QUEUE1删除的节点。

让我们从节点A开始检查图形。

1.将A添加到QUEUE1, 将NULL添加到QUEUE2。

QUEUE1 = {A}
QUEUE2 = {NULL}

2.从QUEUE1中删除节点A, 并插入其所有邻居。将节点A插入QUEUE2

QUEUE1 = {B, D}
QUEUE2 = {A}

3.从QUEUE1中删除节点B, 然后插入其所有邻居。将节点B插入QUEUE2。

QUEUE1 = {D, C, F} 
QUEUE2 = {A, B}

4.从队列1中删除节点D, 然后插入其所有邻居。由于F是已插入的唯一邻居, 因此我们将不再插入。将节点D插入QUEUE2。

QUEUE1 = {C, F}
QUEUE2 = { A, B, D}

5.从队列1中删除节点C, 然后插入其所有邻居。将节点C添加到QUEUE2。

QUEUE1 = {F, E, G}
QUEUE2 = {A, B, D, C}

6.从QUEUE1中删除F并添加其所有邻居。由于已经添加了它的所有邻居, 因此我们将不再添加它们。将节点F添加到QUEUE2。

QUEUE1 = {E, G}
QUEUE2 = {A, B, D, C, F}

7.从QUEUE1中删除E, 所有E的邻居都已添加到QUEUE1中, 因此我们将不再添加它们。所有节点都被访问, 并且目标节点即E遇到了QUEUE2。

QUEUE1 = {G}
QUEUE2 = {A, B, D, C, F, E}

现在, 使用QUEUE2中可用的节点从E回溯到A。

最小路径为A→B→C→E。