What is the difference between DFS and BFS? Where can I apply each?

DFS, or Depth First Search traverses a graph - which is any set of interconnected nodes 'depth first'. It tries to go all the way to the end, and if it fails returns back to the last intersection that it didn't try. BFS, or Breadth First Search, traverses a graph by only going to the next set of nodes from it's current set. In effect it goes to all the nodes of distance one from the starting node, and in the next step goes to all nodes 2 from the starting node. The applications of each depend heavily on the use case. If the nodes we were looking for are deep in the graph, using BFS could be impractical as it could potentially take a long time. If solutions are rare, and can be anywhere in the graph, BFS would be significantly faster than DFS. DFS also has the added advantage of giving metrics such as shortest distance from the starting point, meanwhile the same metric in DFS would be harder to implement.

TD
Answered by Tutor86199 D. Python tutor

4134 Views

See similar Python Mentoring tutors

Related Python Mentoring answers

All answers ▸

How do I use for loops in Python?


Write a program that can convert between celcius and farenheit temperature scales


Given a list of N numbers, use a single list comprehension to produce a new list that only contains those values that are: (a) even numbers, and (b) from elements in the original list that had even indices .


Write a function that checks whether a number is prime or not.


We're here to help

contact us iconContact ustelephone icon+44 (0) 203 773 6020
Facebook logoInstagram logoLinkedIn logo

© MyTutorWeb Ltd 2013–2025

Terms & Conditions|Privacy Policy
Cookie Preferences