Problem Solving Basis - DFS, BFS

DFS (Depth First Search) and BFS (Breadth First Search).

Template Code (Python)

DFS

def dfs(graph, v, visited, dst):
  # 1. check in
  visited[v] = True
  print(v, end=" ")
  # 2. arrived?
  # 3. iterate
  for i in graph[v]:
    # 4. next
    if not visited[i]:
      # 5. visit
      dfs(graph, i, visited, dst)
      # 6. check out

BFS

def bfs(graph, src, visited, dst):
  queue = deque([src])
  visited[src] = True

  while queue:
    # 1. pop
    v = queue.popleft()
    print(v, end=" ")
    # 2. arrived?
    # 3. iterate
    for i in graph[v]:
      # 4. next
      if not visited[i]:
        # 5. visit, enqueue
        queue.append(i)
        visited[i] = True

Complexity Analysis

• Time: O(N), as our task is to traverse all N nodes.
• Space: O(logN) for DFS, as DFS only stores the single path, and O(N) for BFS as all nodes can be pushed to the queue.

link

python: https://github.com/carrtesy/CodingTest_python/blob/main/DFS_BFS/dfs_bfs_template.py