Sets in Code

A set is an unordered collection of unique elements — no duplicates. In Python, sets are written with curly braces {} or set(). Key property: membership testing is O(1) — very fast.

my_set = {1, 2, 3, 4, 5}
empty_set = set()   # Note: {} creates an empty DICT, not a set

# Basic operations
my_set.add(6)         # {1, 2, 3, 4, 5, 6}
my_set.remove(3)      # {1, 2, 4, 5, 6}  — raises KeyError if not found
my_set.discard(99)    # No error if not found
print(4 in my_set)    # True — O(1) lookup

Set Operations

A = {1, 2, 3, 4}
B = {3, 4, 5, 6}

union        = A | B    # {1, 2, 3, 4, 5, 6}  — all elements
intersection = A & B    # {3, 4}               — elements in both
difference   = A - B    # {1, 2}               — in A but not B
sym_diff     = A ^ B    # {1, 2, 5, 6}         — in one but not both

print(A.issubset({1, 2, 3, 4, 5}))  # True — A ⊆ {1..5}
print(A.issuperset({1, 2}))         # True — A ⊇ {1, 2}

When to Use Sets

• Removing duplicates from a collection: list(set(my_list))
• Fast membership testing: x in my_set is O(1) vs O(n) for lists
• Set maths: union, intersection, difference for comparing collections
• Tracking "visited" nodes in graph traversal (very common use case)

Maps / Dictionaries

A map (dictionary in Python) stores key-value pairs. Each key is unique; keys are immutable (strings, numbers, tuples). Values can be any type. Lookup by key is O(1) using a hash table.

student = {'name': 'Alice', 'grade': 'A', 'score': 95}

# Access
print(student['name'])          # 'Alice'
print(student.get('age', 0))   # 0 — default if key not found (no KeyError)

# Modify
student['grade'] = 'A*'        # update value
student['age'] = 17            # add new key-value pair
del student['score']           # remove key

# Iteration
for key, value in student.items():
    print(key, ':', value)

# Check key exists
if 'name' in student:
    print("Name:", student['name'])

Dictionary Methods

Adjacency List using Dictionaries

Graphs can be stored as dictionaries where each key is a node and the value is a list (or set) of neighbours:

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
print(graph['B'])  # ['A', 'D', 'E'] — neighbours of B

Graph Traversal in Code

Graph traversal visits every reachable node starting from a given source. The two standard algorithms are BFS and DFS, implemented using a queue and stack respectively.

Breadth-First Search (BFS) Implementation

BFS visits nodes level by level. Uses a queue (FIFO). Finds the shortest path (in terms of edges) in an unweighted graph.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    order = []

    while queue:
        node = queue.popleft()     # dequeue from front (FIFO)
        order.append(node)

        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)  # enqueue to back

    return order

result = bfs(graph, 'A')   # ['A', 'B', 'C', 'D', 'E', 'F']

Depth-First Search (DFS) Implementation

DFS explores as deep as possible before backtracking. Can be implemented with an explicit stack or recursively (call stack acts as the stack).

# Iterative DFS using explicit stack
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    order = []

    while stack:
        node = stack.pop()         # pop from top (LIFO)
        if node not in visited:
            visited.add(node)
            order.append(node)
            for neighbour in graph[node]:
                if neighbour not in visited:
                    stack.append(neighbour)

    return order

# Recursive DFS
def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for neighbour in graph[node]:
        if neighbour not in visited:
            dfs_recursive(graph, neighbour, visited)
    return visited

BFS vs DFS Comparison