Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Basic Graph Algorithms > Depth First Search and Breadth First Search

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

The running time is linear in the size of the graph (O(|V|+|E|)).

See also:

Basic Graph Algorithms

Graphs and Related Data Types

GraphWin for visualizing graphs and graph algorithms


Manual Entries:

Manual Page Basic Graph Algorithms




Please send any suggestions, comments or questions to leda@algorithmic-solutions.com
© Copyright 2001-2003, Algorithmic Solutions Software GmbH