Difference Between DFS And BFS In Artificial Intelligence

What Is DFS (Depth First Search)?

Depth First search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root (top) node of a tree and goes as far as it can down a given branch (path), then backtracks until it finds an unexplored path, and then explores it. The algorithm does this until the entire graph has been explored.

Depth First Search (DFS) are normally used as subroutines in other more complex algorithms. Hopcroft-Karp, tree-traversal and matching algorithm are examples of algorithm that use DFS to find a matching in a graph.

What Is BFS (Breadth First Search)

Breadth First search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root and explores all the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

Breadth First Search (BFS) is an important search algorithm that is used to solve many problems including finding the shortest path in graph and solving puzzle games (such as Rubik’s Cubes). In computer science, it can also be used to solve graph problems such as analyzing networks, mapping routes and scheduling.

DFS (Depth First Search) Features

• DFS starts the traversal from the root node and explore the search as far as possible from the root node i.e depth wise.
• DFS algorithm works in two stages. In the first stage, the visited vertices are pushed onto the stack and later on when there is no vertex further to visit those that are popped-off.
• DFS search can be done with the help of stack i.e LIFO implementations.
• DFS is not useful in finding shortest path. It is used to perform a traversal of general graph and the idea of DFS is to make a path as long as possible and then go back (backtrack) to add branches also as long as possible.
• DFS is comparatively faster when compared to BFS.
• The time complexity of DFS is O(V+E) where V stands for vertices and E stands for edges.
• DFS requires comparatively less memory to BFS.
• Some Applications of DFS include: Topological sorting, Finding connected components, Finding articulation points (cut vertices) of the graph, Solving puzzles such as maze and Finding strongly connected components.