Depth First Search and Breadth First Search

What is DFS and BFS?

Depth First Search (DFS) and Breadth First Search (BFS) are powerful methods to explore a graph in a systematic way.

Both methods start in a node v of a directed graph and visit all nodes that can be reached from v. The methods differ in the order in which they visit the nodes:

• DFS first explores the edges out of the node most recently reached, that is, it tries to go as deep as possible first.
• BFS explores the edges in the order in which their source node is reached. It explores all edges out of the current node first and then goes to the next node.

Where can I use DFS and BFS?

DFS and BFS can always be used when it is necessary to explore directed graphs in a systematic way.

Example of how to use DFS and BFS

Running Time

See also:

Basic Graph Algorithms

Graphs and Related Data Types

GraphWin for visualizing graphs and graph algorithms

Manual Entries:

Manual Page Basic Graph Algorithms