Geek Answers Handbook

BFS & DFS - where to start from?

I read pages and pages with information about BFS and DFS algorithms. What none of them says, is this top the first?

For example, in this image, the arrows mean that you cannot move from c to b, but can move from b to c?

search network

Your help is greatly appreciated, friends.

+4
source share
3 answers

If it is not a directed graph, it does not matter. The graph you published is a directed graph, which means what you indicated. You can go from a to b, but not from b to a.

Regarding the selection of a node in a directed graph, each node that you select can lead to a different result. Usually in these conditions it is best to start with the root of the node, if one is specified.

+1
source

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

Which of the vertices should I choose as the initial vertex? - Depends upon your requirement .

An example :

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

  • If you want to find whether vertex K is accessible from vertex S or not, in this case too you must run BFS / DFS from source vertex S.

  • If you want to solve the Rat problem in the maze , in which the rat starts from source S and must achieve the goal using DFS, then again you have to run the DFS algorithm from Source S.

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

An example :

  • When searching for a strongly connected component (SCC) of a directed graph, we run DFS, choosing any vertex as the source vertex.

  • Performing topological sorting of a directed acyclic graph using DFS, we can again select any vertex as the initial vertex.

Thus, which vertex for selection is not fixed at first and depends on the nature of the problem, we solve with DFS and BFS.

+5
source

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 do not need to specify which nodes to start with DFS with, as you will iterate over all the nodes anyway.

DFS process:

 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.

Thus, he finally visits every node on the chart. A similar rationale for BFS.

+1
source

More articles:


All Articles