BFS & DFS - Which vertex to start with? [closed]

Question

I've read pages and pages of information on BFS and DFS algorithms. What none of them say, is which vertex to choose first?

For instance, in this image, do the arrows mean you cannot traverse from c to b, but can traverse from b to c?

Your help is much appreciated, friends.

Answer 1

Breadth-first_search and Depth-first_search can be started with any source Vertex S.

Which of the vertex to select as a source vertex?-Depends upon your requirement.

Example:

1. If you want to find the shortest path from Source S to all of the other vertex using BFS(for graph with all edges having same cost or unweighted graph).Then you should select S as source vertex.

2. If you want to find whether vertex K is reachable from vertex S or not, in this case too you have to start your BFS/DFS from source vertex S.

3. If you want to solve Rat in a Maze problem in which a rat starts from source S and has to reach destination using DFS, then again you have to start the DFS algorithm from Source S.

In some Cases, We are free to choose any vertex as a source vertex.

Example:

1. While Finding Strongly Connected Component(SCC) of a directed graph, we start DFS by selecting any vertex as a Source Vertex.

2. While performing a Topological Sort of a Directed Acyclic Graph using DFS, again we are free to select any vertex as a Source Vertex.

Thus, Which vertex to choose first is not fixed and depends upon the nature of the problem , we are solving with DFS and BFS.

Answer 2

do the arrows mean you cannot traverse from c to b, but can traverse from b to c?

This is a directed graph, Yes.

You don't need to specify which node to start with when you do DFS since you will iterate over all the nodes anyway.

The process of DFS is:

DFSmain(G):
     For v=1 to n: if v is not yet visited, do DFS(v).

DFS(v):
   mark v as visited. // entering node v
   for each unmarked out-neighbor w of v: do DFS(w).
   return. // exiting node v.

So it will finally visit every node in the graph. Similar rationale for BFS.