DSA sheet · Graphs · Concepts

Introduction to Graphs: the terms you need

Before any graph question, the teacher goes through the words and tools that every later video uses: directed vs undirected, cycles, edge weights, the three ways to store a graph (and why we nearly always pick the adjacency list), the visited array, grids, in-degree for dependency questions, the difference between undirected and bidirectional, and connected components. None of these is hard on its own, but if one is fuzzy, every later problem feels hard. This page is the dictionary for the whole graph topic.

This is a concept video, so the 9 steps are adapted:
what a graph is → the terms (each with a picture) → the ways to store it (with code) → the tools every algorithm uses (visited, in-degree, components) → which problems use what → remember

• Part 0 · What a graph is
• Part A · Directed vs undirected
• Part B · Cycles (and the directed graph that only looks cyclic)
• Part C · Edge weights, and "no path"
• Part D · Storing a graph: edge list → adjacency matrix → adjacency list
• Part E · The visited array
• Part F · Grids: graphs where you don't store children
• Part G · In-degree: dependency questions
• Part H · The degree-sum formula
• Part I · Undirected vs bidirectional
• Part J · Connected components
• Part K · Revision page

Part 0 · What a graph is

1Nodes and edges

A graph is a set of nodes (also called vertices) with some pairs of them joined. Each join is an edge. We write V for the number of nodes and E for the number of edges.

  (1)———(2)
   |   /
   |  /         4 nodes: 1, 2, 3, 4
  (3)———(4)     4 edges: 1-2, 1-3, 2-3, 3-4

2How it differs from a tree

• A tree has a root, a fixed place to start. A graph has none; the question tells you where to start.
• A tree never has a cycle (a way to walk around and come back). A graph may have one; above, 1–2–3–1 is a cycle.
• A tree is a special graph. As soon as a cycle appears, it is no longer a tree.

Where graphs come from (patterns video): road maps, computer networks, anything where things are linked to or depend on each other.

Part A · Directed vs undirected

1The idea

(3)———(2)———(1)

(3)——→(2)——→(1)

• Undirected: an edge between 1 and 2 means you can go 1 → 2 and 2 → 1. Either one can act as the "parent" and the other as the "child".
• Directed: the arrow is a rule. From 3 you can go to 2. From 2 you can go to 1, but not back to 3, because that edge points the other way.

2What changes in code

Only how we save each edge. For an undirected edge (u, v) we save both directions. For a directed edge u → v we save one.

def build_undirected(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)      # u can reach v
        adj[v].append(u)      # and v can reach u
    return adj

def build_directed(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)      # only u -> v
    return adj

Part B · Cycles

1What a cycle is

A cycle means: start at some node, walk along edges, and arrive back at the same node.

• In an undirected graph you may walk each edge either way, so any closed loop of edges is a cycle. (You can't use the same edge to go out and straight back; that isn't a loop.)
• In a directed graph you must follow the arrows all the way round.

2The teacher's trap: it looks like a cycle, but isn't

(1)——→(2)
 |      ↑
 ↓      |
(4)←——(3)

(1)——→(2)
 ↑      |
 |      ↓
(4)←——(3)

Left picture: the four edges form a closed square, but try every start. From 1 you reach 2 and 4, and they lead nowhere. From 3 you reach 2 and 4, then stop. Going 2 → 3 is against the arrow. You can never get back to your start, so there is no cycle.

Right picture: we change the arrows so they all point the same way round: 1 → 2 → 3 → 4 → 1. Now from any node, following the arrows brings you home: cycle.

3A brute-force check, just to make the definition concrete

def has_directed_cycle(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
    for start in range(n):              # try every node as the start
        seen = set()
        stack = list(adj[start])        # take at least one step first
        while stack:
            x = stack.pop()
            if x == start:
                return True             # followed arrows back home
            if x not in seen:
                seen.add(x)
                stack.extend(adj[x])
    return False

This is O(V · (V + E)), slow but simple. The proper O(V + E) method comes in Problem 12. Nodes here are 0-based: square A is edges [[0,1],[2,1],[2,3],[0,3]] → False; square B is [[0,1],[1,2],[2,3],[3,0]] → True.

Part C · Edge weights

1The idea

An edge with a number on it is weighted: the number is the cost (distance, time, money) of walking it. If no number is written, every edge costs 1.

(A)—2—(B)—1—(C)—2—(D)
       |
       3
       |
      (E)—4—(F)

Undirected: A to D costs 2 + 1 + 2 = 5, and D to A costs the same 5, because you can walk the same edges back.

2Directed and weighted: sometimes there is no path

(A)—2→(B)—1→(C)—2→(D)
       ↑
       3
       |
      (E)—4→(F)

A → D still works (cost 5). But A → F? From A you can only go to B, then C, then D. The edge between B and E points into B, so you can't go down it. Even though edges exist "near" F, the arrows don't let you reach it. The question tells you what to return then: often −1, sometimes 0 or "infinity".

3In code

def build_weighted(edges, directed):
    adj = {}
    for u, v, w in edges:
        adj.setdefault(u, []).append((v, w))       # store (neighbour, cost)
        if not directed:
            adj.setdefault(v, []).append((u, w))
    return adj

def path_cost(adj, path):
    total = 0
    for a, b in zip(path, path[1:]):               # each step a -> b
        costs = [w for v, w in adj.get(a, []) if v == b]
        if not costs:
            return -1                              # this step is not allowed
        total += min(costs)
    return total

With the directed edges above: path_cost(adj, "ABCD") = 5, and path_cost(adj, "ABEF") = −1, because B → E goes against the arrow. Finding the cheapest path is Dijkstra's job (Problem 25).

Part D · Storing a graph

1Why we need to store "children" at all

To traverse a graph (BFS or DFS, next videos) we keep asking one question: "I'm at node x; where can I go next?" The nodes you can go to are x's neighbours (the teacher calls them children). The question usually gives the edges as a plain list:

Her example graph, with nodes 1…6 and 7 edges:

(6)——(2)——(1)——(5)
        \   /     |
         (3)————(4)

edges = [[1,3], [1,2], [1,5], [4,5], [4,3], [2,3], [2,6]]

2Way 1: search the edge list every time (too slow)

To find 1's neighbours, scan every pair and keep those that contain 1. That's O(E) for one node. Then do the same for 2, for 3… If the pairs are not sorted, the ones for node 1 can be anywhere, so you must scan the whole list every time. For all N nodes that's about N × N = O(N²) work just to find children.

def neighbours_by_scan(edges, x):
    out = []
    for u, v in edges:          # the WHOLE list, for every single question
        if u == x:
            out.append(v)
        elif v == x:
            out.append(u)
    return out

3Way 2: adjacency matrix

Make an N × N table mat, all 0. For each edge (u, v), set mat[u][v] = 1 and mat[v][u] = 1. The table is filled "in both directions" because the graph is undirected. It is built in one pass over the edge list. With weights, you'd store the weight instead of 1.

Row = "from", column = "to". Node 1's neighbours: walk row 1 and pick the columns that hold 1 → 2, 3, 5.

def build_matrix(n, edges):
    mat = [[0] * (n + 1) for _ in range(n + 1)]   # row/col 0 unused (1-based nodes)
    for u, v in edges:
        mat[u][v] = 1
        mat[v][u] = 1                               # undirected: both cells
    return mat

def neighbours_from_matrix(mat, x):
    return [y for y in range(len(mat)) if mat[x][y] == 1]   # scans a whole row

4Way 3: adjacency list (what we almost always use)

Scan the edge list once. For each edge (u, v), add v to u's list and u to v's list. Afterwards, node x's neighbours are just adj[x], already packed together with nothing wasted.

• If the question gives the number of nodes n, make a list of n lists (index = node).
• If it doesn't (or the nodes are names/strings), use a dictionary: the key is the node, the value is its list.

from collections import defaultdict

def build_list(n, edges):              # nodes 1..n are known
    adj = [[] for _ in range(n + 1)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    return adj

def build_dict(edges):                 # nodes not known in advance
    adj = defaultdict(list)            # a missing key starts as []
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    return adj

On her edges: 1 → [3, 2, 5], 2 → [1, 3, 6], 3 → [1, 4, 2], 4 → [5, 3], 5 → [1, 4], 6 → [2].

Part E · The visited array

1Why

Start at 1: its neighbours are 3, 2, 5. Go to 5: its neighbours are 1 and 4. If we go to 1 again, we get 3, 2, 5 again, then 5 sends us to 1 again… an endless loop. Undirected edges and cycles both lead you back to old nodes.

So we keep a visited array, one slot per node, all 0/False at the start. When we're done with a node we set its slot to 1/True. Before stepping onto a neighbour, we check its slot. From 5: is 1 visited? Yes → skip. Is 4 visited? No → go.

2Code

def reachable(adj, start):
    visited = [False] * len(adj)
    visited[start] = True
    todo = [start]
    order = []
    while todo:
        x = todo.pop()
        order.append(x)
        for y in adj[x]:
            if not visited[y]:          # the check that prevents the loop
                visited[y] = True
                todo.append(y)
    return order

The exact order (BFS or DFS) is the topic of the next two videos; here only the visited idea matters. On her graph, sorted(reachable(build_list(6, edges), 1)) = [1, 2, 3, 4, 5, 6].

Part F · Grids: graphs where you don't store children

1The idea

Many questions give a 2D grid (a matrix of cells). Each cell is a node. If the question says you may move up, down, left, right, then the neighbours of cell (i, j) are known by formula:

            (i-1, j)
               ↑
  (i, j-1) ← (i, j) → (i, j+1)
               ↓
            (i+1, j)

No adjacency list is needed: the neighbours are computed on the spot. You only must stay inside the grid (the bounds check).

2Code

DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]      # up, down, left, right

def grid_neighbours(rows, cols, i, j):
    out = []
    for dr, dc in DIRS:
        r, c = i + dr, j + dc
        if 0 <= r < rows and 0 <= c < cols:    # bounds check
            out.append((r, c))
    return out

In a 3 × 3 grid: the corner (0, 0) has 2 neighbours, an edge cell (0, 1) has 3, and the centre (1, 1) has 4. In grid questions the "visited" mark is often written straight into the grid (e.g. turning land '1' into '0').

Part G · In-degree: dependency questions

1The kind of question

Questions like Course Schedule I and II: some tasks must be finished before others. No start node is given. Instead you must start with a task that depends on nothing. Her example:

• to start 1, finish 2 first
• to start 2, finish 3 first
• to start 3, finish 4 and 5 first
• to start 4, finish 5 first
• to start 5, finish 6 first

2In-degree = how many things I'm still waiting for

Draw an arrow from the task that must come first to the task that waits for it: "u waits for v" becomes v → u. Then the in-degree is the number of arrows coming into a node. A node with in-degree 0 is free to start; here that's only 6.

(6)→(5)→(4)→(3)→(2)→(1)
      \________↗

3Releasing tasks one by one

1. 6 has in-degree 0 → do 6. Tell its children: 5's in-degree 1 → 0, so 5 is free.
2. Do 5. Its children are 3 and 4. 3: 2 → 1 (still waiting for 4). 4: 1 → 0, so 4 is free.
3. Do 4. Its child 3: 1 → 0, so 3 is free now (both 4 and 5 are done).
4. Do 3 → 2 is free. Do 2 → 1 is free. Do 1.

Order: 6, 5, 4, 3, 2, 1. This "keep a queue of in-degree-0 tasks" method is Kahn's algorithm (topological sort, Problems 21–24).

from collections import deque

def task_order(n, needs):            # needs = [[u, v], ...] means u needs v first
    children = [[] for _ in range(n + 1)]
    indeg = [0] * (n + 1)
    for u, v in needs:
        children[v].append(u)        # v -> u : v finishing releases u
        indeg[u] += 1                # u waits for one more task
    queue = deque(x for x in range(1, n + 1) if indeg[x] == 0)
    order = []
    while queue:
        x = queue.popleft()
        order.append(x)              # x is done
        for c in children[x]:
            indeg[c] -= 1            # c waits for one task fewer
            if indeg[c] == 0:
                queue.append(c)      # c is free now
    return order if len(order) == n else []   # [] = impossible (a cycle)

task_order(6, [[1,2],[2,3],[3,4],[3,5],[4,5],[5,6]]) → [6, 5, 4, 3, 2, 1].

4When it's impossible: a dependency cycle

Add "6 needs 5" to the list. Now 5 waits for 6 and 6 waits for 5. Neither will ever reach in-degree 0, so it's a deadlock. Nothing at all can start, since every task depends on 5 or 6 in the end. The queue starts empty and the order is shorter than n → answer "impossible". Questions ask either "give the order" (Course Schedule II) or "can all be finished?" (Course Schedule I).

Part H · The degree-sum formula

For each node, count the edges touching it. On her 6-node graph: 1 → 3, 2 → 3, 3 → 3, 4 → 2, 5 → 2, 6 → 1. The total is 14, and the graph has 7 edges. The total is always 2 × the number of edges, because each edge has two ends and adds 1 to each.

def degree_sum(n, edges):
    deg = [0] * (n + 1)
    for u, v in edges:
        deg[u] += 1                  # one end of the edge
        deg[v] += 1                  # the other end
    return sum(deg)

Part I · Undirected vs bidirectional

Both let you move in both directions, but they are not the same thing:

(A)⇄(B)——→(C)        A→C ✓ (via B)   B→A ✓   C→B ✗

In code, a bidirectional edge is just two directed edges, each with its own cost:

def build_bidirectional(pairs):
    adj = {}
    for u, v, cost_uv, cost_vu in pairs:
        adj.setdefault(u, []).append((v, cost_uv))
        adj.setdefault(v, []).append((u, cost_vu))   # may differ from cost_uv
    return adj

The teacher calls it a very minor difference. It matters mostly when the costs differ.

Part J · Connected components

1The idea

A graph may be in several separate pieces. Each piece is a connected component: inside it everyone can reach everyone, and there's no edge to other pieces. Her picture: one city with three colonies that have no roads between them.

(1)—(2)—(3)—(4)      (5)—(6)       (8)—(9)—(10)
                       \  /
                        (7)

2Counting them

1. Start a traversal at 1. It marks 1, 2, 3, 4. From 4 there's only 3, already visited, so it can't reach 5. One piece → count = 1.
2. The next unvisited node is 5. A traversal marks 5, 6, 7. From 7 we're back at 5 (already visited) → count = 2.
3. Next unvisited: 8. It marks 8, 9, 10 → count = 3.

The number of times we had to start a new traversal = the number of components. The traversal can be DFS or BFS; it just has to mark everything reachable.

def count_components(n, edges):        # nodes 1..n
    adj = [[] for _ in range(n + 1)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    visited = [False] * (n + 1)

    def dfs(x):                        # mark everything reachable from x
        visited[x] = True
        for y in adj[x]:
            if not visited[y]:
                dfs(y)

    count = 0
    for start in range(1, n + 1):
        if not visited[start]:         # a node no earlier call reached
            count += 1                 # = a new piece
            dfs(start)
    return count

count_components(10, [[1,2],[2,3],[3,4],[5,6],[6,7],[7,5],[8,9],[9,10]]) → 3. Problems built on this: Number of Provinces, Number of Islands, and other "count the groups" questions.

Part K · Revision page

The teacher's study tip: write your own notes while watching and revise them often; DSA is forgotten in weeks without revision.

edges = [[1, 3], [1, 2], [1, 5], [4, 5], [4, 3], [2, 3], [2, 6]]
print(build_list(6, edges)[1])                       # [3, 2, 5]
print(neighbours_from_matrix(build_matrix(6, edges), 1))   # [2, 3, 5]
print(degree_sum(6, edges))                          # 14
print(task_order(6, [[1,2],[2,3],[3,4],[3,5],[4,5],[5,6]]))   # [6, 5, 4, 3, 2, 1]
print(task_order(2, [[1,2],[2,1]]))                  # []
print(count_components(10, [[1,2],[2,3],[3,4],[5,6],[6,7],[7,5],[8,9],[9,10]]))   # 3
print(has_directed_cycle(4, [[0,1],[2,1],[2,3],[0,3]]))   # False
print(grid_neighbours(3, 3, 0, 0))                   # [(1, 0), (0, 1)]

Based on this video: Graph Basics: Terms You Must Know