宽度优先在有向图中搜索

When performing a breadth first search on a directed graph, and we begin at vertex 1 in the picture below, will vertex 0 ever be visited?

在有向图上执行广度优先搜索时，我们从下图中的顶点1开始，是否会访问顶点0？

              >v4------>v5 
            /
v0------->v1
            \
             > v2-------v3

Also, can you guys please confirm with me if I have the concept of BFS? So if we started at v1, we first consider all unexplored paths (in this case the paths from v1 to v4, and v1 to v2, but NOT v1 to v0 because it isn't possible), then we visit the vertices v4 and v2, and order does not matter. Then, depending on which ever vertex was last visited, we check for unexplored paths (if we're at v4, the unexplored path would be from v4 to v5, so we travel along that and then visit v5). After that, we check v2 for unexplored paths, in this case v2 to v3, and visit v3. Now v3 does not have any other unexplored paths so we check v5, which also does not have any unexplored paths. Now do we end our BFS? Or can we somehow visit v0?

另外，如果我有BFS的概念，请你们跟我确认一下吗？因此，如果我们从v1开始，我们首先考虑所有未探测的路径（在这种情况下是从v1到v4的路径，从v1到v2，但不是v1到v0，因为它是不可能的），然后我们访问顶点v4和v2 ，顺序无所谓。然后，根据上次访问过哪个顶点，我们检查未探测的路径（如果我们在v4，未探测的路径将从v4到v5，所以我们沿着那个路径然后访问v5）。之后，我们检查v2是否有未探测的路径，在本例中为v2到v3，并访问v3。现在v3没有任何其他未开发的路径，所以我们检查v5，它也没有任何未探测的路径。现在我们结束我们的BFS了吗？或者我们可以以某种方式访问v0？

Also, if instead we had used a DFS and started at v1, would we then eventually visit v0? If DFS was used, would the order of vertices visited, assuming v2 is left of v1, be v1,v2,v3,v4,v5, and then v0?

另外，如果我们使用了DFS并从v1开始，那么我们最终会访问v0吗？如果使用了DFS，假设v2是v1，那么访问顶点的顺序是v1，v2，v3，v4，v5，然后是v0吗？

1 个解决方案

#1

Your understanding of the BFS appears to be correct. DFS is also correct (up to vertex v5).

您对BFS的理解似乎是正确的。 DFS也是正确的（直到顶点v5）。

In neither case would you arrive at v0 if you start at v1 as there is no directed edge leading into v0 in your diagram.

在这两种情况下，如果从v1开始，你都不会到达v0，因为图中没有有向边通向v0。

#1