Adjacency List

    adjList = {    
        1: [2],    
        2: [1, 3, 4],    
        3: [2, 4],    
        4: [2, 3, 5],    
        5: [4]    
    }    

Constructing Adjacency Lists

{
    0: [1, 3, 2],
    1: [0, 2],
    2: [1, 3, 0],
    3: [2, 0]
}

Solution

def build_adj_list(n, edges):
    adj_list = {i: [] for i in range(n)}
    for u, v in edges:
        adj_list[u].append(v)
        adj_list[v].append(u)
        
    return adj_list

DFS on an Adjacency List

1. Each node can have any amount of neighbors, so we need a for loop to iterate over each neighbor rather than making calls to the left and right children of the current node.
2. Because graphs can contain cycles, we need to keep track of nodes we have already visited. If we encounter a node that has already been visited, we should return immediately without making any further recursive calls (or skip it in the loop altogether). Otherwise, we may end up in an infinite loop.
3. We don't need an explicit base case like we do in the trees. Eventually, we will visit all nodes in the graph, and the recursion will stop on its own (with the help of the visited set).

adjList = {
    "1": ["2", "4"],
    "2": ["1", "3"],
    "3": ["2", "4"],
    "4": ["1", "3", "5"],
    "5": ["4"]
}

def dfs(adjList):
  if not adjList:
    return
  visited = set()
  def dfs_helper(node):
    if node in visited:
      return
    visited.add(node)
    for neighbor in adjList[node]:
      dfs_helper(neighbor)
    return
  # Handle disconnected components
  for node in adjList:
    if node not in visited:
      dfs_helper(node)

Summary

• Use a set to keep track of visited nodes. Each time you visit a node, add it to the set.
• If you encounter a node that has already been visited, return immediately without making any further recursive calls.
• Use a for loop to iterate over each neighbor of the current node, and recursively call dfs on each neighbor.