What is the difference between depth-first-search and breadth-first-search?

Why does DFS visit

BFS vs. DFS

1)BFS Stands for “Breadth First Search”. DFS stands for “Depth First Search”.

2) BFS starts traversal from the root node and then explore the search in the level by level manner i.e.
as close as possible from the root node.

DFS starts the traversal from the root node and explore the search as far as possible from the root
node i.e. depth wise.

3)Breadth First Search can be done with the help of queue i.e. FIFO implementation.

Depth First Search can be done with the help of Stack i.e. LIFO implementations.

4)This algorithm works in single stage. The visited vertices are removed from the queue and then
displayed at once.

This 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 are popped-off.

5)BFS is slower than DFS.

DFS is more faster than BFS.

6)BFS requires more memory compare to DFS.

DFS require less memory compare to BFS.

7)Applications of BFS
> To find Shortest path
> Single Source & All pairs shortest paths
> In Spanning tree
> In Connectivity

Applications of DFS
> Useful in Cycle detection
> In Connectivity testing
> Finding a path between V and W in the graph.
> useful in finding spanning trees & forest.

8)BFS is useful in finding shortest path.BFS can be used to find the shortest distance between some
starting node and the remaining nodes of the graph.

DFS in not so useful in finding shortest path. It is used to perform a traversal of a 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.
9)Algorithm:

Breadth First Search (BFS) algorithm traverses a graph in a breadthward motion and uses a queue to
remember to get the next vertex to start a search, when a dead end occurs in any iteration.

As in the example given above, BFS algorithm traverses from A to B to E to F first then to C and G
lastly to D. It employs the following rules.

 Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a
queue.
 Rule 2 − If no adjacent vertex is found, remove the first vertex from the queue.
 Rule 3 − Repeat Rule 1 and Rule 2 until the queue is empty.

Depth First Search (DFS) algorithm traverses a graph in a depthward motion and uses a stack to
remember to get the next vertex to start a search, when a dead end occurs in any iteration.

As in the example given above, DFS algorithm traverses from S to A to D to G to E to B first, then to F
and lastly to G. It employs the following rules.

 Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a stack.
 Rule 2 − If no adjacent vertex is found, pop up a vertex from the stack. (It will pop up all the
vertices from the stack, which do not have adjacent vertices.)
 Rule 3 − Repeat Rule 1 and Rule 2 until the stack is empty.
 Minimal Spanning Tree and Shortest PathTree Problems
We consider in this section two problems defined for an undirected graph. Since they are similar, the problems are often
mistaken for one another. Both can be solved by greedy algorithms.

The Minimal Spanning Tree Problem

Consider the undirected network as shown in the figure. The graph consists of nodes and edges, and each edge has an
associated length. An edge is the line segment connecting two nodes and has the same length in either direction.

Original Graph

The Minimal Spanning Tree problem is to select a set of edges so that there is a path between each node. The sum of the
edge lengths is to be minimized.

When the edge lengths are all nonnegative, as assumed here, the optimum selection of edges forms a spanning tree.
Because of this characteristic of the solution, the problem is called the minimum spanning tree problem. The problem can
be solved with a greedy algorithm called Prim's Algorithm. Click the link below to see the statement of the algorithm and
a demonstration.

Prim's Algorithm

The Minimal Spanning Tree Problem

Find the set of edges connecting all nodes such that the sum of the edge length is minimized

GREEDY ALGORITHM FOR MST

Initial

Select any node arbitrarily and let this node alone form the set S1. Put all other nodes in the set S2.

Selection

From all the edges with one end in the set S1 and the other end in the set S2, select the one with the smallest length. Let
this edge be (i, j).
Add this edge to the spanning tree. Add node j to the set S1 and delete it from the set S2.

Finish

If the set S1 includes all the nodes, stop with the minimum spanning tree. Otherwise repeat the Selection step.

The algorithm is one of the simplest in optimization theory. The optimum is found after m 1 performances of the selection
step, where m is the number of nodes.

The Shortest Path Tree Problem

We consider again the same undirected graph, but now we solve a different problem. The graph consists of nodes and
edges, and each edge has an associated length. In this problem we identify a root node and desire to find a path to each
node from the root node such that the length of the path to each node is minimized.

The Shortest Path Tree problem is to find the set of edges connecting all nodes such that the sum of the edge lengths from
the root to each node is minimized

Again assume all edge lengths are nonnegative. The optimum selection of edges forms a spanning tree. The problem can
be solved with a greedy algorithm called Dijkstra's Algorithm. Click the link below to see the statement of the algorithm
and a demonstration.

Dijkstra's Algorithm

The Shortest Path Tree Problem

GREEDY ALGORITHM FOR SPT

Initial

Select the root node to form the set S1. Assign the path length 0 to this node. Put all other nodes in the set S2.

Selection
Compute the lengths of the paths to all nodes directly reachable from S1 through a node in S1. Select the node in S2 with
the smallest path length.

Let the edge connecting this node with S1 be (i, j). Add this edge to the shortest path tree. Add node j to the set S1 and
delete it from the set S2.

Finish

If the set S1 includes all the nodes, stop with the shortest path tree. Otherwise repeat the Selection step.

The algorithm is adapted easily to directed networks with nonnegative arc lengths. The optimum is found after m 1
performances of the selection step.

Comparing the Minimal Spanning Tree and Shortest Path Trees.

The figure shows the solutions to the minimal spanning tree and shortest path tree for the example problem. The solutions
differ in their selection of edges, because the criteria for optimality for the two problems are different.

Minimal Spanning Tree Shortest Path Tree from Node 1