algorithm - 了解 BFS 的运行时间复杂度

Question

我很难理解 BFS 算法时间复杂度的一个要素。

对于无向图，我的教授说每条边 (u,v) 被遍历两次。一次来自 u 的方向，一次来自 v 的方向。因此，找到与至少一个顶点相邻的所有未标记顶点的步骤是 O(|E|)。

有人能解释一下如何在有向图中每条边遍历一次而在无向图中遍历两次吗？我想，对于 BFS，我们只是从根顶点向外移动？这第二次遍历来自哪里？

Answer 1

假设您使用邻接表来存储图形。

Breadth-First-Search(Graph, root):
 2 
 3     for each node n in Graph:            
 4         n.distance = INFINITY        
 5         n.parent = NIL
 6 
 7     create empty queue Q      
 8 
 9     root.distance = 0
10     Q.enqueue(root)                      
11 
12     while Q is not empty:        
13     
14         current = Q.dequeue()
15     
16         for each node n that is adjacent to current:
17             if n.distance == INFINITY:
18                 n.distance = current.distance + 1
19                 n.parent = current
20                 Q.enqueue(n)

在无向图中，v 和 u 在彼此的邻接表中。所以在第 16 行中，当我们检查相邻节点时，当当前节点是 u 时，我们检查相邻节点 v 并且当当前节点是 u 我们检查相邻节点 v。但这并不意味着我们再次将 v 插入队列。我们只是检查一下。

但是在无向图中只有 v 在 u 的邻接表中。所以每条边 u->v 都会被检查一次。

我假设您的教授的意思是我们检查每条边两次而不是遍历。