DFS Depth First Search on Graph in DSA Python - Build from Scratch

DFS Depth First Search on Graph

📖 Scenario: You are exploring a map of connected cities represented as a graph. Each city is a node, and roads between cities are edges. You want to visit all cities reachable from a starting city using Depth First Search (DFS).

🎯 Goal: Build a program that performs DFS on a graph represented by an adjacency list. You will create the graph, set the starting city, implement DFS to visit connected cities, and print the order of visited cities.

📋 What You'll Learn

Create a graph as a dictionary with exact city connections

Set a starting city variable

Implement DFS using recursion and a visited set

Print the list of visited cities in the order they were visited

💡 Why This Matters

🌍 Real World

Graph traversal algorithms like DFS are used in navigation systems, social networks, and solving puzzles.

💼 Career

Understanding DFS is fundamental for software engineers working with graphs, trees, and network data structures.

1

Create the graph as an adjacency list

Create a dictionary called graph with these exact entries: 'A': ['B', 'C'], 'B': ['D'], 'C': ['E'], 'D': [], 'E': []

DSA Python

# Create the graph dictionary with the given city connections
# Your code here

Hint

Think of the graph as a dictionary where each city points to a list of connected cities.

2

Set the starting city for DFS

Create a variable called start_city and set it to the string 'A'

DSA Python

graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['E'],
    'D': [],
    'E': []
}
# Set the starting city for DFS
# Your code here

Hint

The starting city is where your DFS will begin. Use the exact variable name start_city.

3

Implement DFS function

Define a function called dfs that takes parameters city, graph, and visited. Inside, add city to visited. Then use a for loop with variable neighbor to iterate over graph[city]. For each neighbor not in visited, call dfs(neighbor, graph, visited). Finally, create an empty list called visited_cities and call dfs(start_city, graph, visited_cities).

DSA Python

graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['E'],
    'D': [],
    'E': []
}
start_city = 'A'
# Define the dfs function and call it
# Your code here

Hint

Use recursion to visit each city and keep track of visited cities in a list.

4

Print the visited cities

Write a print statement to display the visited_cities list

DSA Python

graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['E'],
    'D': [],
    'E': []
}
start_city = 'A'

def dfs(city, graph, visited):
    visited.append(city)
    for neighbor in graph[city]:
        if neighbor not in visited:
            dfs(neighbor, graph, visited)

visited_cities = []
dfs(start_city, graph, visited_cities)
# Print the visited cities list
# Your code here

Hint

The output should show the order in which cities were visited by DFS starting from 'A'.

Practice

1. What does DFS (Depth First Search) do when exploring a graph?

easy

A. It explores as far as possible along each branch before backtracking.

B. It explores all neighbors at the current depth before going deeper.

C. It visits nodes randomly without any order.

D. It only visits nodes with the highest value first.

Solution

1. Step 1: Understand DFS traversal

   DFS explores a graph by going deep into one branch before backtracking to explore others.

2. Step 2: Compare with other traversal methods

   BFS explores neighbors level by level, but DFS goes deep first.

3. Final Answer:

   It explores as far as possible along each branch before backtracking. -> Option A

4. Quick Check:

   DFS = deep exploration first [OK]

Hint: DFS means go deep first, then backtrack [OK]

Common Mistakes:

• Confusing DFS with BFS
• Thinking DFS visits nodes randomly
• Assuming DFS visits nodes by value

2. Which of the following is the correct Python syntax to start a DFS function on a graph represented as adjacency list graph from node start?

easy

A. def dfs(start, graph):

B. def dfs(graph, start):

C. def dfs(graph):

D. def dfs(start):

Solution

1. Step 1: Identify required parameters for DFS

   DFS needs the graph and the starting node to begin traversal.

2. Step 2: Check function signature correctness

   def dfs(graph, start): correctly defines a function with parameters (graph, start).

3. Final Answer:

   def dfs(graph, start): -> Option B

4. Quick Check:

   DFS needs graph and start node [OK]

Hint: DFS function needs graph and start node parameters [OK]

Common Mistakes:

• Swapping parameter order incorrectly
• Missing one of the parameters
• Using only one parameter when two are needed

3. What is the output of the following DFS traversal starting from node 0?

graph = {0: [1, 2], 1: [2], 2: [0, 3], 3: [3]}
visited = set()
def dfs(node):
    if node not in visited:
        print(node, end=' ')
        visited.add(node)
        for neighbor in graph[node]:
            dfs(neighbor)
dfs(0)

medium

A. 0 3 2 1

B. 0 2 3 1

C. 0 1 3 2

D. 0 1 2 3

Solution

1. Step 1: Start DFS from node 0

   Visit 0, mark visited. Neighbors: 1, 2.

2. Step 2: Visit neighbor 1

   Visit 1, mark visited. Neighbor: 2.

3. Step 3: Visit neighbor 2

   Visit 2, mark visited. Neighbors: 0 (visited), 3.

4. Step 4: Visit neighbor 3

   Visit 3, mark visited. Neighbor: 3 (already visited).

5. Final Answer:

   0 1 2 3 -> Option D

6. Quick Check:

   DFS order = 0 1 2 3 [OK]

Hint: Follow neighbors depth-first, avoid revisiting nodes [OK]

Common Mistakes:

• Visiting neighbors in wrong order
• Revisiting already visited nodes
• Confusing BFS order with DFS

4. Find the error in this DFS code snippet and select the fix:

graph = {0: [1], 1: [2], 2: []}
visited = set()
def dfs(node):
    if node in visited:
        return
    print(node)
    for neighbor in graph[node]:
        dfs(neighbor)
dfs(0)

medium

A. Add 'visited.add(node)' after printing node to mark it visited.

B. Change 'if node in visited' to 'if node not in visited'.

C. Remove the 'return' statement inside the if condition.

D. Add 'visited.remove(node)' after recursive calls.

Solution

1. Step 1: Identify missing visited marking

   The code never adds nodes to visited, so it revisits nodes infinitely.

2. Step 2: Fix by adding visited marking

   Adding 'visited.add(node)' after printing marks node as visited to avoid revisits.

3. Final Answer:

   Add 'visited.add(node)' after printing node to mark it visited. -> Option A

4. Quick Check:

   Mark visited after visiting node [OK]

Hint: Always add node to visited set after visiting [OK]

Common Mistakes:

• Forgetting to mark nodes visited
• Incorrect if condition logic
• Removing nodes from visited incorrectly

5. Given a directed graph represented as adjacency list:

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

Write the DFS traversal order starting from node 0 that detects cycles by tracking recursion stack. What is the order of nodes visited before detecting a cycle?

hard

A. 0 1 2

B. 0 2 3 1

C. 0 1 2 3

D. 0 2 1 3

Solution

1. Step 1: Start DFS from node 0 and track recursion stack

   Visit 0, then 1, then 2, then 3. At 3, neighbor 1 is in recursion stack, cycle detected.

2. Step 2: List nodes visited before cycle detection

   Nodes visited in order: 0, 1, 2, 3 before cycle found.

3. Final Answer:

   0 1 2 3 -> Option C

4. Quick Check:

   DFS with cycle detection visits 0 1 2 3 [OK]

Hint: Track recursion stack to detect cycles during DFS [OK]

Common Mistakes:

• Ignoring recursion stack for cycle detection
• Stopping traversal too early
• Visiting nodes in wrong order