CODEWITHSUNDEEP
c++searchgraphdepth-first-searchbreadth-first-search
Vincent Stevenson
Vincent Stevenson

Reputation: 53

Breadth first search in directed graph

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?

              >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?

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?

Upvotes: 2

Views: 1811

Answers (1)

jc746
jc746

Reputation: 11

Your understanding of the BFS appears to be correct. DFS is also correct (up to vertex 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.

Upvotes: 1

Related Questions