Graph Traversal | Depth-first & Breadth-first

Graph traversal is the process of visiting (to check or update) every node in a graph. It is important to be familiar with graph traversing methods when creating an application, since there are many things that can be optimized or achieved with this structure, like search features, network connections, web crawling, games, etc. Two methods for graph traversing are depth-first and and breadth-first.

Depth-first

In a depth-first algorithm for traversing graphs, one starts at the root and makes this the first element in the stack, then one must traverse to a neighboring node, if this has not yet been ‘discovered’, it should be added to the stack as well. This process must be repeated until the current node being visited has no more unvisited neighbors. When this happens, a backtracking process must start, following the stack’s order.

Pseudocode

This code implements depth-first search algorithm.

procedure DFS(start: graph, searchItem: node to find in graph) is
stack <- [start];
visited <- [];
currNode = start;
while(length(stack) is not 0) do
currNode <- stack's last index;
if(currNode === searchItem) then
return currNode;
end if conditional;
if(visited does not contain currNode) then
add currNode to visited;
for all neighbors of currNode do
add neighbor to stack;
end for all loop;
end if conditional;
if(length(stack) === 0) then
return false;
end if conditional;
end while loop;
end procedure;

Big O and space complexities

Worst time complexity O(|V|+|E|)

Worst space complexity O(|V|)

Where |V| is the number of vertices (nodes), and |E| is the number of edges (neighbors).

Usage examples

  • Maze generation
  • Topological sorting
  • Game development
  • Network connections (ex. LinkedIn connections, Facebook’s mutual friends).

Breadth-first

In this type of graph traversing algorithm one starts at the root node and explores it’s neighbors first, adding them to the queue if they have not been visited yet. You must keep doing this until there is no more unvisited nodes. When there are no more unvisited nodes, you make the first element on the queue your current node until your queue is empty. When your queue is empty, you are done.

Pseudocode

procedure BFS(start) is
path <- [start];
queue <- [start];
while(length(queue) is not 0) do
currNode <- queue's first element;
for all neighbors of currNode do
if(path does not contain neighbor) then
add neighbor to path;
add neighbor to queue;
end if conditional;
end for all loop;
end while loop
if(length(queue) is 0) then
return path;
end if conditional
end procedure;

Big O and space complexities

Worst time complexity O(|V|+|E|)

Worst space complexity O(|V|)

Where |V| is the number of vertices (nodes), and |E| is the number of edges (neighbors).

Usage examples

  • Finding a user’s closest connections
  • Finding shortest path between two nodes
  • Peer-to-peer networks
  • Broadcasting in network