How to find the shortest path in an unweighted graph? How to find a path through a maze? How to determine if a graph is connected? Using two popular graph traversal algorithms, depth first search and breadth first search. DFS and BFS are both methods of graph traversal, meaning to "visit" the nodes of a graph via the edges. We start at one node and then follow edges to discover all nodes in a graph.

Depth-First Search

Essentially, DFS explores a single path and deep as it can before starting a new path.

  1. 1  Choose an arbitrary vertex and mark it visited.

  2. 2  From the current vertex, proceed to an unvisited, adjacent vertex and mark it visited.

  3. 3  Repeat 2nd step until a vertex is reached which has no adjacent, unvisited vertices (dead-end).

  4. 4  At each dead-end, backtrack to the last visited vertex and proceed down to the next unvisited, adjacent vertex.

  5. 5  The algorithm halts there are no unvisted vertices.

 

Adjacency matrices:O(|V|2)

It is a graph traversal, so we need to iterate over all vertices (|V| of these). For each vertex, we need to check the neighbours of it. For the matrix represenation, the only way we can guranatee to find all neighbours of vertex i is to do a linear scan across its row in the matrix, which has |V| elements. So |V| * |V| gives O(|V|2)complexity. The traversal also needs to setup visited status, which requires O|V | complexity, but the quadratic term dominates.

Adjacency lists:O(|V|+|E|)

Similarly to the matrix representation, we need to iterate over all the vertices (|V| of these). For each vertex, we need to check the neighbours of it. Different for the adjacency list represenation, we only need to scan through the elements in the associated linked list. The total number of elements across all the linked list (and total number of neighbours to consider) is O(|E|). The traversal also needs to setup visited status, which requires O|V | complexity. Hence the total is O(|V| + |E|).

Breadth-First Search

  1. 1  Choose an arbitrary vertex v and mark it visited.

  2. 2  Visit and mark (visited) each of the adjacent (neighbour) vertices of v in turn.

  3. 3  Once all neighbours of v have been visited, select the first neighbour that was visited, and visit all its (unmarked) neighbours.

  4. 4  Then select the second visited neighbour of v, and visit all its unmarked neighbours.

  5. 5  The algorithm halts when we visited all vertices.

  DFS BFS
Application Connectivity, Acyclicity Connectivity, Acyclicity, Shortest paths
Efficiency for adjacency matrix Θ(|V2|) Θ(|V2|)
Efficiency for adjacency list Θ(|V| + |E|) Θ(|V| + |E|)