Graph Traversal

One of graph algorithms' main applications is finding the shortest path given two nodes u and v. This section describes some algorithms that can be used to achieve this goal. The most famous and with several applications are depth-first search (DFS), breadth-first search (BFS), and Djikstra. For extension, another two approaches: Bellman-Ford and A*.

Breadth-First Search

The Breadth-First Search (BFS) algorithm explores a graph by visiting all nodes at the current depth before moving on to nodes at the next depth level. It utilizes a queue data structure to store and expand nodes in a first-in, first-out manner. Starting from a root node, BFS systematically visits its immediate neighbors, then their unvisited neighbors, and so on, until all reachable nodes have been explored. This process effectively covers the graph layer by layer, ensuring that nodes closer to the root are visited before those farther away.

Time complexity: $O(n + m)$ in the worst case, where $n$ is the number of vertices and $m$ is the number of edges.

from collections import defaultdict
 
def bfs(graph, start_node):
  queue = [start_node]
  visited = set()
 
  while queue:
    node = queue.pop(0)
    if node not in visited:
      visited.add(node)
      queue.extend(graph[node])
 
  return visited

Depth-First Search

DFS explores a graph by going deeper and deeper along a single path until it reaches a dead end. It then backtracks and explores another path. This makes it suitable for tasks like finding connected components, topological sorting, and cycle detection.

Time complexity: $O(n + m)$ in the worst case, similar to BFS.

def dfs(graph, node, visited=None):
  if visited is None:
    visited = set()
  visited.add(node)
  # Process node here
  for neighbor in graph[node]:
    if neighbor not in visited:
      dfs(graph, neighbor, visited)

Dijkstra's

Dijkstra's algorithm finds the shortest paths from a single source node to all other nodes in a weighted graph with non-negative edge weights. It uses a priority queue to select the next node to explore, prioritizing nodes with the smallest tentative distance.

** Time complexity**: $O(nlog(m))$ in the worst case with a priority queue implementation.

def dijkstra(graph, source):
  distances = {node: float('inf') for node in graph}
  distances[source] = 0
  queue = [(0, source)]
  visited = set()
  while queue:
    (cost, node) = heapq.heappop(queue)
    if node not in visited:
      visited.add(node)
      for neighbor in graph[node]:
        if neighbor not in visited:
          new_cost = cost + graph[node][neighbor]
          if new_cost < distances[neighbor]:
            distances[neighbor] = new_cost
            heapq.heappush(queue, (new_cost, neighbor))
  return distances

A*

A* is an informed search algorithm that combines the logic of Dijkstra's algorithm with a heuristic function. This function estimates the remaining cost to reach the goal from a given node. A* prioritizes nodes with lower estimated total cost, making it more efficient than Dijkstra's in many cases.

Time complexity: $O(n log (m))$ in the worst case with a priority queue implementation.

def a_star(graph, start, goal, heuristic):
  queue = [(heuristic(start), start)]
  visited = set()
  while queue:
    (cost, node) = heapq.heappop(queue)
    if node == goal:
      return cost
    if node not in visited:
      visited.add(node)
      for neighbor in graph[node]:
        if neighbor not in visited:
          neighbor_cost = cost + graph[node][neighbor]
          heapq.heappush(queue, (neighbor_cost + heuristic(neighbor), neighbor))

Bellman-Ford

Bellman-Ford is an algorithm that can find the shortest paths in a graph even if it contains negative edges. It works by iteratively relaxing all edges in the graph until no further improvement can be made.

Time complexity: $O(nm)$ in the worst case.

def bellman_ford(graph, source):
  distances = {node: float('inf') for node in graph}
  distances[source] = 0
  for _ in range(len(graph) - 1):
    for u in graph:
      for v in graph[u]:
        distances[v] = min(distances[v], distances[u] + graph[u][v])
  return distances

Minimum Spanning Tree

Prim's

Kruskal's

Connectivity

Union-Find

Topological Sort

Kahn's

Depth-First Search

Matching

Hopcroft-Karp