Skip to content

Graph Traversals

Sar Champagne Bielert edited this page Apr 8, 2024 · 13 revisions

These traversal algorithms are conceptually the same as the ones introduced in the tree section.

Depth first search

In a depth first search, we start with an arbitrary node as a root and explore each neighbor fully before exploring the next one.

Implementation:

'''
Assuming we have a directed graph represented with an adjacency list.

Example:
graph = {'A': ['B', 'C'],  
 'B': ['D', 'E'],  
 'C': ['F'],  
 'E': ['F']}
'''
  
def depth_first_search(graph, start):  
    visited, stack = set(), [start] 
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            # If a node with no outgoing edges won't be 
            # included in the adjacency list, we need to check
            if vertex in graph:
                for neighbor in graph[vertex]:
                    if neighbor not in visited:
                        stack.append(neighbor)
    return visited

Runtime: O(V + E), where V = number of nodes/vertices and E = number of edges

Example interview question using DFS:

Breadth first search

In breadth first search, we pick an arbitrary node as the root and explore each of its neighbors before visiting their children. Breadth first search is the better suited at finding the shortest path between two nodes.

Implementation:

from collections import deque

'''
Assuming we have a directed graph represented with an adjacency list.

Example:
graph = {'A': ['B', 'C'],  
 'B': ['D', 'E'],  
 'C': ['F'],  
 'E': ['F']}
'''
  
def breadth_first_search(graph, start):  
    visited, queue = set(), deque(start)
    while queue:
        vertex = queue.popleft()
        visited.add(vertex)
        # If a node with no outgoing edges won't be 
        # included in the adjacency list, we need to check
        if vertex in graph:
           for neighbor in graph[vertex]:
              if neighbor not in visited:
                 queue.append(neighbor)
    return visited

Example interview question using BFS:

Runtime: O(V + E), where V = number of nodes/vertices and E = number of edges

See explanation of why it's O(V + E).

Key Takeaways

  • DFS is better for analyzing structure of graphs (ex. looking for cycles)
  • BFS is better for optimization (ex. shortest path algorithms)

References

Clone this wiki locally