了解 BFS 的 运行 时间复杂度
Understanding the Running Time Complexity of BFS
我很难理解 BFS 算法时间复杂度的一个要素。
对于无向图，我的教授说每条边 (u,v) 被遍历两次。一次从u的方向，一次从v的方向。因此，找到与至少一个顶点相邻的所有未标记顶点的步骤是 O(|E|).
谁能解释一下如何在有向图中每条边遍历一次，在无向图中遍历两次？我想，对于 BFS，我们只是从根顶点向外移动？这第二次遍历是从哪里来的？
假设您使用邻接表来存储图形。
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 都会被检查一次。
我假设你的教授的意思是我们检查每条边两次而不是遍历。
我很难理解 BFS 算法时间复杂度的一个要素。
对于无向图，我的教授说每条边 (u,v) 被遍历两次。一次从u的方向，一次从v的方向。因此，找到与至少一个顶点相邻的所有未标记顶点的步骤是 O(|E|).
谁能解释一下如何在有向图中每条边遍历一次，在无向图中遍历两次？我想，对于 BFS，我们只是从根顶点向外移动？这第二次遍历是从哪里来的？
假设您使用邻接表来存储图形。
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 都会被检查一次。
我假设你的教授的意思是我们检查每条边两次而不是遍历。