# Graph Traversal

Learn about BFS and DFS searching algorithms.

In this section we present two algorithms for exploring a graph, starting at one of its vertices, `i`

, and finding all vertices that are reachable from `i`

. Both of these algorithms are best suited to graphs represented using an adjacency list representation. Therefore, when analyzing these algorithms we will assume that the underlying representation is `AdjacencyLists`

.

## Breadth-first search

The **breadth-first-search** algorithm starts at a vertex `i`

and visits, first the neighbours of `i`

, then the neighbours of the neighbours of `i`

, then the neighbours of the neighbours of the neighbours of `i`

, and so on.

This algorithm is a generalization of the breadth-first traversal algorithm for binary trees, and is very similar; it uses a queue, `q`

, that initially contains only `i`

. It then repeatedly extracts an element from `q`

and adds its neighbours to `q`

, provided that these neighbours have never been in `q`

before. The only major difference between the breadth-first-search algorithm for *graphs* and the one for *trees* is that the algorithm for graphs has to ensure that it does not add the same vertex to `q`

more than once. It does this by using an auxiliary boolean array, `seen`

, that tracks which vertices have already been discovered.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy