Graph traversals

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)

Example interview question using DFS:

• Detect a cycle in a graph

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)

Key Takeaways:

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