SCPC Week 10 Tutorial: Intro to Graphs

Graph Fundamentals

What is a graph?

Graphs are used to model objects and their connections. E.g.:

Application	Examples
Social networks	Instagram, Facebook, etc.
Transportation networks	Train maps, flight networks
Computer networks	The Internet, electrical circuits

Where do graph problems come from?

Objects	Connections	Example problem
People	Friendships	Can person A reach person B?
Rooms	Doors	Is there a way out of the building?
Grid cells	Legal moves	What is the fewest number of steps?

If the problem involves objects and connections, try drawing a graph.

Vertices and edges

A graph is a set of vertices and edges between them.

Undirected: A — B. An edge goes from A to B and from B to A.
Directed: A → B. An edge goes from A to B.

Paths, cycles, and connected components

Path: A → B → C. A sequence of connected vertices.
Cycle: A → B → C → A. A path that returns to its start.
Connected component: one connected group, with no path to a different group. For example, in a graph with edges A—B and C—D, {A, B} and {C, D} are separate components.

Reading a graph

Transform the problem input into a graph and an adjacency list.

Example input (1-based):

The first line gives the number of vertices and edges. The remaining lines give the edges.

Edges: 1—2, 1—4, 2—3, 2—4.

Neighbours (1-based):

1: [2, 4]
2: [1, 3, 4]
3: [2]
4: [1, 2]

Undirected edges appear in the lists of both endpoint vertices.

Building an adjacency list

Both snippets read an undirected graph with input vertices labelled 1 through n and store vertices with zero-based indexing.

C++

int n, m;
cin >> n >> m;
vector<vector<int>> adj(n);

for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u - 1].push_back(v - 1);
    adj[v - 1].push_back(u - 1);
}

Python

n, m = map(int, input().split())
adj = [[] for _ in range(n)]

for _ in range(m):
    u, v = map(int, input().split())
    adj[u - 1].append(v - 1)
    adj[v - 1].append(u - 1)

Remove the second push_back / append for a directed edge.

Why use adjacency lists?

Representation	Space	Full traversal
Adjacency list
Adjacency matrix

Here, n is the number of vertices and m is the number of edges.
For most beginner contest problems, start with an adjacency list.

Graph Traversal

DFS

Depth First Search (DFS)

The core idea of DFS is to keep moving to an unvisited neighbour. If all neighbours have been visited, return to the previous node (backtrack).

Example tree:

A possible DFS order (visiting neighbours in the illustrated order):
0 → 1 → 3 → 4 → 2 → 5

Tracing DFS by hand

Step	Node	Reason
1	0	Start at the root
2	1	Go to the first child
3	3	Go deeper again
4	4	Backtrack to 1, then take the next child
5	2	Backtrack to 0
6	5	Visit the remaining subtree

When a node has no unvisited child, recursion returns.

DFS in Python (recursive)

def dfs(s):
    if visited[s]:
        return
    visited[s] = True
    print(s)          # process s
    for u in adj[s]:
        dfs(u)

DFS in Python (iterative)

def dfs(start):
    stack = [start]

    while stack:
        s = stack.pop()
        if visited[s]:
            continue
        visited[s] = True
        print(s)  # process s

        for u in reversed(adj[s]):
            if not visited[u]:
                stack.append(u)

DFS in C++

void dfs(int s) {
    if (visited[s])
        return;
    visited[s] = true;
    cout << s << endl; // Process node s
    for (auto u: adj[s])
        dfs(u);
}

Complete DFS example in Python

n, m = map(int, input().split())
adj = [[] for _ in range(n)]

for _ in range(m):
    u, v = map(int, input().split())

    adj[u - 1].append(v - 1)
    adj[v - 1].append(u - 1)

visited = [False] * n

def dfs(start):
    stack = [start]
    order = []
    while stack:
        s = stack.pop()
        if visited[s]:
            continue
        visited[s] = True
        order.append(s)
        for u in reversed(adj[s]):
            if not visited[u]:
                stack.append(u)
    return order

for v in dfs(0):
    print(v + 1, end=" ")

Sample: n = 6, edges 1-2, 1-3, 2-4, 2-5, 3-6 → output 1 2 4 5 3 6.

Complete DFS example in C++

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> adj;
vector<int> visited, order;

void dfs(int s) {
    if (visited[s]) 
        return;

    visited[s] = 1;
    order.push_back(s);
    for (int u : adj[s])
        dfs(u);
}

int main() {
    int n, m;
    cin >> n >> m;
    adj.resize(n);
    visited.assign(n, 0);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;

        adj[u - 1].push_back(v - 1);
        adj[v - 1].push_back(u - 1);
    }
    dfs(0);
    for (int u : order)
        cout << u + 1 << ' ';
    cout << '\n';
}

Sample: n = 6, edges 1-2, 1-3, 2-4, 2-5, 3-6 → output 1 2 4 5 3 6.

Counting connected components

Run DFS once from every vertex that has not been visited.

Python

visited = [False] * n
components = 0
for v in range(n):
    if not visited[v]:
        dfs(v)
        components += 1
print(components)

Important things to remember for DFS

Mark as visited before the recursive calls. Otherwise a cycle can send you round forever.
Restart DFS for disconnected graphs. One call only reaches nodes connected to its start.

BFS

BFS explores layer by layer

Visit all nodes one edge away for the current node before moving to the next layer.

Example tree:

BFS visit order: 0 → 1 → 2 → 3 → 4 → 5.
The core idea of BFS is to explore layer by layer, visiting all nodes in the current layer before moving on to the next.

What is happening inside the queue?

Example: BFS from 0, with neighbours considered in ascending order.

Pop	Queue afterwards	New nodes
Start	`[0]`	`dist[0] = 0`
`0`	`[1, 2]`	`1` and `2`
`1`	`[2, 3, 4]`	`3` and `4`
`2`	`[3, 4, 5]`	`5`
`3`	`[4, 5]`	—
`4`	`[5]`	—
`5`	`[]`	Completed

Queue rule: First in, first out.

BFS in Python

Use collections.deque for an efficient queue.

from collections import deque

def bfs(start):
    q = deque([start])
    visited[start] = True
    dist[start] = 0
    while q:
        s = q.popleft()
        print(s)
        for u in adj[s]:
            if visited[u]:
                continue
            visited[u] = True
            dist[u] = dist[s] + 1
            q.append(u)

BFS in C++

void bfs(int x) {
    visited[x] = true;
    dist[x] = 0;
    queue<int> q;
    q.push(x);
    while (!q.empty()) {
        int s = q.front();
        q.pop();
        cout << s << endl; // Process node s
        for (auto u : adj[s]) {
            if (visited[u])
                continue;
            visited[u] = true;
            dist[u] = dist[s] + 1;
            q.push(u);
        }
    }
}

Complete BFS example in Python

from collections import deque

n, m = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    adj[u - 1].append(v - 1)
    adj[v - 1].append(u - 1)

visited = [False] * n
dist = [-1] * n

def bfs(start):
    q = deque([start])
    visited[start] = True
    dist[start] = 0
    order = []
    while q:
        s = q.popleft()
        order.append(s)
        for u in adj[s]:
            if visited[u]:
                continue
            visited[u] = True
            dist[u] = dist[s] + 1
            q.append(u)
    return order

for v in bfs(0):
    print(v + 1, end=" ")

Sample: n = 6, edges 1-2, 1-3, 2-4, 2-5, 3-6 → output 1 2 3 4 5 6.

Complete BFS example in C++

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
vector<int> visited, dist, order;

void bfs(int start) {
    queue<int> q; q.push(start);
    visited[start] = 1; dist[start] = 0;
    while (!q.empty()) {
        int s = q.front(); q.pop();
        order.push_back(s);
        for (int u : adj[s]) {
            if (visited[u]) continue;
            visited[u] = 1;
            dist[u] = dist[s] + 1;
            q.push(u);
        }
    }
}

int main() {
    int n, m; cin >> n >> m;
    adj.resize(n);
    visited.assign(n, 0);
    dist.assign(n, -1);
    for (int i = 0; i < m; ++i) {
        int u, v; 
        cin >> u >> v;
        adj[u - 1].push_back(v - 1);
        adj[v - 1].push_back(u - 1);
    }
    bfs(0);
    for (int u : order)
        cout << u + 1 << ' ';
    cout << '\n';
}

Sample: n = 6, edges 1-2, 1-3, 2-4, 2-5, 3-6 → output 1 2 3 4 5 6.

Why BFS finds a shortest path

In an unweighted graph, the shortest path means the fewest edges.

Target node: Suppose we want the shortest path from 0 to 5 in the illustrated tree.
BFS result: dist[5] = 2, so the path length is 2 edges.

BFS visits nodes in increasing distance from the source (layer by layer). Hence, the first time we visit 5 we are guaranteed to have the minimum number of edges.

How do we print the path itself?

A parent array lets us reconstruct the route.

Add this when discovering a neighbour (C++ syntax):

parent[u] = s;   // store where u came from

Example parent array:

Node	0	1	2	3	4	5
Parent	-1	0	0	1	1	2

Reconstructing 0 → 5:

Start at 5.
parent[5] = 2
parent[2] = 0
parent[0] = -1

So we read 5 → 2 → 0, then reverse it.

Final path: 0 → 2 → 5.

Applying Graph Traversals

DFS or BFS?

Both take time with adjacency lists.

If you need to…	Use
Check whether `t` is reachable from `s`	Both
Count components in an undirected graph	Both
Find a shortest path in an unweighted graph	BFS
Explore a recursive path of the graph	DFS

A grid is also a graph

Each open cell is a node. Moving up, down, left, or right creates edges.

Illustrative grid from the slide (S = start, T = target, # = blocked):

S . # .
. . # .
# . # .
. . . T

Generating neighbours:

for dr, dc in [(1,0), (-1,0),
               (0,1), (0,-1)]:
    nr, nc = r + dr, c + dc
    if 0 <= nr < H and 0 <= nc < W:
        if grid[nr][nc] != "#":
            # visit and enqueue (nr, nc)

Apply BFS to find the fewest moves, or DFS to test reachability.

Common mistakes

Most graph wrong answers are implementation details.

Mistake	Check
Directed vs undirected	Should you add 1 edge or 2 edges?
1-based vs 0-based	Are the vertices in the input data 1-based or 0-based?
Visited at discovery	In BFS, mark visited when pushing into the queue.
Wrong shortest-path algorithm	BFS only works on unweighted edges! Weighted edges needs something else…
Disconnected nodes	Do you need to do a traversal starting from every node?

Concepts adapted from COMP2823 Week 7 - Graphs (Julian Mestre).