[Algo] Graph Traversal Template

graph_traversal_template.py

# Iterative
def dfs(graph, start):
  visited, stack = set(), [start]
  while stack:
    node = stack.pop()
    visited.add(node)
    for neighbor in graph[node]:
      if not neighbor in visited:
        stack.append(neighbor)
  return visited

# Recursive
def dfs(graph, start):
  def dfs_recursive(graph, start, visited):
    visited.add(start)
    for neighbor in graph[start]:
      if not neighbor in visited:
        dfs_recursive(graph, neighbor, visited)
  visited = set()
  return dfs_recursive(graph, start, visited)

def bfs(graph, start):
  visited, queue = set(), deque(start)
  while queue:
    node = queue.popleft()
    visited.add(node)
    for neighbor in graph[node]:
      if not neighbor in visited:
          queue.append(neighbor)
  return visited

# Topological sort
# Current node comes before any of its neighbor
def top_sort(graph):
  def dfs_recursive(graph, start, visited, sorted_nodes)
    visited.add(start)
    for neighbor in graph[start]:
      if not neighbor in visited:
        dfs_recursive(graph, neighbor, visited)
    sorted_nodes.appendleft(start)

  sorted_nodes, visited = deque(), set()
  for node in graph:
    dfs_recursive(graph, node, visited, sorted_nodes)
  return sorted_nodes