Graph Basics 10 XP Easy

Ctrl+Enter Run Ctrl+S Save

A Graph is a collection of nodes (vertices) connected by edges. Graphs model relationships everywhere: social networks (friends), maps (roads), the internet (links)! 🌐

💡 Think of it like this: Think of a city map. Each city is a node, and each road between cities is an edge. Some roads are one-way (directed), others go both ways (undirected).

# Most common representation: Adjacency List
# Each node maps to a list of its neighbors
graph = {
    0: [1, 2],     # Node 0 connects to 1 and 2
    1: [0, 3],     # Node 1 connects to 0 and 3
    2: [0, 4],     # Node 2 connects to 0 and 4
    3: [1],
    4: [2]
}

#   0 --- 1 --- 3
#   |
#   2 --- 4

Two main ways to explore a graph:

🌊 BFS (Breadth-First Search): Visit level by level using a QUEUE. Best for shortest path!
🏊 DFS (Depth-First Search): Go as deep as possible, then backtrack. Uses recursion or STACK.
👁️ Both need a visited set to avoid infinite loops in cycles!

💭 Your turn! Take what you learned above and write the code yourself. Struggling is part of learning! 🧠

Graph problems are ~25% of coding interviews! Master BFS and DFS, and you'll handle: Number of Islands, Course Schedule, Shortest Path, and many more.

📋 Instructions

Build a graph as an adjacency list from edges, then perform BFS from node 0. Edges: [[0,1],[0,2],[1,3],[2,4]] Print nodes in BFS order.

Create a defaultdict(list), add both directions for each edge. Use collections.deque for BFS, popleft and add unvisited neighbors.

⚠️ Try solving it yourself first — you'll learn more!

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node, end=' ')
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

🧪 Test Cases

Input

bfs(0)

Expected

[0, 1, 2, 3, 4]

Test case 1

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›