Strongly connected components in Data Structures Theory - Mini Project: Build & Apply

Understanding Strongly Connected Components

📖 Scenario: Imagine you have a map of cities connected by one-way roads. You want to find groups of cities where you can travel from any city to any other city within the same group using these roads.

🎯 Goal: You will build a simple representation of a directed graph and identify its strongly connected components (SCCs). This means finding groups of nodes where each node is reachable from every other node in the same group.

📋 What You'll Learn

Create a directed graph using a dictionary where keys are city names and values are lists of cities reachable by one-way roads

Add a helper variable to keep track of visited cities during traversal

Implement the core logic to find strongly connected components using depth-first search (DFS)

Complete the structure by adding a final step to store or mark the strongly connected components

💡 Why This Matters

🌍 Real World

Strongly connected components help in understanding networks like social media, web pages, or transportation systems where mutual reachability is important.

💼 Career

Knowledge of graph theory and strongly connected components is useful for software engineers, data scientists, and network analysts working on complex systems and algorithms.

1

Create the directed graph

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

Data Structures Theory

# Create the graph dictionary with the specified cities and roads
# Your code here

Need a hint?

Use a dictionary where each key is a city and the value is a list of cities it connects to by one-way roads.

2

Add a visited set

Create an empty set called visited to keep track of cities you have already checked during traversal.

Data Structures Theory

graph = {
    'A': ['B'],
    'B': ['C', 'E', 'F'],
    'C': ['D', 'G'],
    'D': ['C', 'H'],
    'E': ['A', 'F'],
    'F': ['G'],
    'G': ['F'],
    'H': ['D', 'G']
}

# Create an empty set called visited
# Your code here

Need a hint?

A set is useful to remember which cities you have already visited to avoid checking them again.

3

Implement DFS to find reachable cities

Define a function called dfs that takes a city node and a set component. Inside the function, add node to visited and component. Then, for each neighbor in graph[node], if the neighbor is not in visited, call dfs recursively with the neighbor and component.

Data Structures Theory

graph = {
    'A': ['B'],
    'B': ['C', 'E', 'F'],
    'C': ['D', 'G'],
    'D': ['C', 'H'],
    'E': ['A', 'F'],
    'F': ['G'],
    'G': ['F'],
    'H': ['D', 'G']
}

visited = set()

def dfs(node, component):
    # Your code here

Need a hint?

Use recursion to visit all connected cities starting from the given node.

4

Find and store strongly connected components

Create an empty list called scc_list. Then, for each city node in graph, if node is not in visited, create an empty set called component, call dfs(node, component), and append component to scc_list.

Data Structures Theory

graph = {
    'A': ['B'],
    'B': ['C', 'E', 'F'],
    'C': ['D', 'G'],
    'D': ['C', 'H'],
    'E': ['A', 'F'],
    'F': ['G'],
    'G': ['F'],
    'H': ['D', 'G']
}

visited = set()

def dfs(node, component):
    visited.add(node)
    component.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, component)

# Create scc_list and find strongly connected components
# Your code here

Need a hint?

Loop through all cities and collect groups of connected cities using DFS.