考虑BFS(从CLRS修改而来(的标准伪代码
def BFS(G, source):
Initialize Boolean array visited to keep track of visited nodes
Mark source as visited
Add source to queue Q
while Q is not empty:
u = Q.dequeue()
for v in G[u]:
if v is not visited:
mark v as visited and add to queue
此版本的BFS在起始顶点source上运行，并将访问从source可到达的所有顶点。然而，如果G具有多个组件，则BFS()不会访问G中的所有顶点。因此，拥有功能对我来说是有意义的
def BFS_wrapper(G):
for source in G:
if source not in visited:
BFS(source)
这将使得BFS能够到达整个图G中的所有顶点(即使G具有多个分量(。然而，BFS的标准伪代码并不包括这个包装器。此外，DFS的标准伪代码似乎总是有这个精确的"包装器"函数，让DFS到达整个图G中的所有顶点，即使G有多个组件。
我的问题是：为什么标准的DFS代码有这个包装函数，而标准的BFS代码没有？DFS似乎意味着在具有多个组件的图上使用，而BFS只意味着在带有单个组件的图中使用。等价地说，为什么BFS似乎不意味着在具有多个组件的图上运行，而DFS是？
用每个组件的一个顶点初始化队列q允许BFS同时探索不同的组件。因此，我们不需要"包装器"函数来赋予BFS探索具有多个组件的图的能力。