Menu
I've read somewhere that DFS is not gaurenteed to find a solution while BFS is.. why? I don't really get how this is true.. could someone demonstrate a case for me that proves this?
843
BFS can be used to find the shortest path, with unit weight edges, from a node (origional source) to another. Whereas, DFS can be used to exhaust all the choices because of its nature of going in depth, like discovering the longest path between two nodes in an acyclic graph.
DFS cannot always guarantee that the solution will be found 2. DFS algorithms conduct searches by exploring the graph one layer at a time 3. BFS always finds optimal solution 4.
Provided that your DFS always traverses the left node first, then your BFS and DFS will be the same. You can extend this logic to any type of tree. If every node has at most one child that also has children, then your DFS and BFS will be the same if in the DFS you always traverse the nodes without children first.
BFS can be used to find a single source shortest path in an unweighted graph because, in BFS, we reach a vertex with a minimum number of edges from a source vertex. In DFS, we might traverse through more edges to reach a destination vertex from a source.
DFS, since its a Depth first search, could get stuck in an infinite branch and never reach the vertex you're looking for. BFS goes through all vertices at the same distance from the root each iteration, no matter what branch they're on so it will find the desired vertex eventually.
example:
root -> v1 -> v2 -> v3 -> ... goes on forever
|-> u.
in this example, if DFS begins at the root and then goes on to v1. it will never reach u since the branch it entered is infinite. BFS will go from root to either v1 or u and then to the other.
195
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
