DFS traversal and applications in Data Structures Theory - Mini Project: Build & Apply

DFS Traversal and Applications

📖 Scenario: You are exploring how to visit all connected points in a network, like checking all friends in a social circle or all connected cities on a map.

🎯 Goal: Build a simple step-by-step understanding of Depth-First Search (DFS) traversal on a graph and see how it helps find connected components.

📋 What You'll Learn

Create a graph using an adjacency list

Set up a visited tracker for nodes

Implement DFS traversal using recursion

Use DFS to count connected components in the graph

💡 Why This Matters

🌍 Real World

DFS helps explore networks like social media connections, maps, or computer networks to find all reachable points from a start.

💼 Career

Understanding DFS is fundamental for software engineers, data scientists, and network analysts to solve problems involving connectivity and traversal.

1

Create the graph as an adjacency list

Create a dictionary called graph representing this undirected graph with these edges: 1-2, 1-3, 2-4, 5-6. Use lists for neighbors.

Data Structures Theory

# Your code here

Need a hint?

Think of the graph as a dictionary where keys are nodes and values are lists of connected nodes.

2

Set up a visited dictionary to track nodes

Create a dictionary called visited with keys as graph nodes and values set to False to mark them unvisited.

Data Structures Theory

graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1],
    4: [2],
    5: [6],
    6: [5]
}
# Your code here

Need a hint?

Use a dictionary comprehension to set all nodes as not visited.

3

Write the DFS function using recursion

Define a function called dfs that takes a node. Mark visited[node] as True. Then for each neighbor in graph[node], if it is not visited, call dfs on that neighbor.

Data Structures Theory

graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1],
    4: [2],
    5: [6],
    6: [5]
}
visited = {node: False for node in graph}
# Your code here

Need a hint?

Use recursion to visit neighbors that are not yet visited.

4

Count connected components using DFS

Create a variable count set to 0. Loop over each node in graph. If visited[node] is False, call dfs(node) and then increase count by 1.

Data Structures Theory

graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1],
    4: [2],
    5: [6],
    6: [5]
}
visited = {node: False for node in graph}

def dfs(node):
    visited[node] = True
    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs(neighbor)

# Your code here

Need a hint?

Each time you find an unvisited node, you start a new connected component.