1. Graphs
Definition – Graph
A graph is a set of vertices and a set of edges , each edge connecting a pair of vertices of . Notation: vertices, edges.
| Kind | Definition |
|---|---|
| Undirected graph | edges have no direction |
| Directed graph (digraph) | vertices are linked by arcs (oriented edges) from an origin to a destination |
| Weighted graph | each edge/arc has a weight (cost) to cross it |
Example – weighted digraph (slide 4, c)
flowchart LR v0((0)) -->|3| v1((1)) v0 -->|4| v4((4)) v2((2)) -->|1| v4 v4 -->|1| v1 v1 -->|2| v3((3)) v3 -->|7| v2
Paths and cycles
| Term | Definition |
|---|---|
| Adjacent vertices | connected by an edge |
| Path | sequence with an edge from to ; its length is |
| Simple path | all vertices distinct |
| Cycle | path of length ≥ 3 connecting to itself |
| Simple cycle | simple path except that first = last vertex |
Definition – Complete graph
An edge between every pair of vertices.
| Graph with vertices | Number of edges |
|---|---|
| Complete undirected | |
| Complete digraph |
Worked example: → 10 edges (undirected), 20 arcs (directed).
2. Graph Implementation
Adjacency matrix
Vertices labeled ; if there is an edge from to , else 0. For a weighted graph, store the weight in . A sparse graph gives a matrix full of 0s.
Adjacency lists
For each vertex, a list of the vertices it is linked to by an edge of which it is the origin.
Worked example – directed graph
Arcs: 0→1, 0→4, 1→3, 2→4, 3→2, 4→1.
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 1 | 1 | |||
| 1 | 1 | ||||
| 2 | 1 | ||||
| 3 | 1 | ||||
| 4 | 1 |
Lists: 0 → [1, 4]; 1 → [3]; 2 → [4]; 3 → [2]; 4 → [1].
Worked example – undirected graph
Edges: 0–1, 0–4, 1–3, 1–4, 2–3, 2–4. The matrix is symmetric:
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 1 | 1 | |||
| 1 | 1 | 1 | 1 | ||
| 2 | 1 | 1 | |||
| 3 | 1 | 1 | |||
| 4 | 1 | 1 | 1 |
Lists: 0 → [1, 4]; 1 → [0, 3, 4]; 2 → [3, 4]; 3 → [1, 2]; 4 → [0, 1, 2].
⚠️ In an undirected graph each edge appears twice (in both lists / both cells).
Space complexity
| Adjacency matrix | Adjacency list | |
|---|---|---|
| Good for | dense graphs, | sparse graphs, |
| Memory | ||
| Fast operation | test if two vertices are connected | list the neighbors of a vertex |
3. Graph Traversals
Visit every vertex exactly once, possibly in an order based on the graph’s topology (used in AI search, shortest paths…).
Depth-First Search (DFS) – stack
Go as deep as possible down a path; back up as little as possible at a dead end (next vertex already marked, or none).
found = false
stack.Push(startVertex); mark startVertex
do
stack.Pop(vertex)
if vertex == endVertex: found = true
else: push all adjacent unmarked vertices; mark them
while !stack.IsEmpty() and !found
if !found: write "Path does not exist"Breadth-First Search (BFS) – queue
Look at all vertices at the same depth before going deeper.
found = false
queue.Enqueue(startVertex); mark startVertex
do
queue.Dequeue(vertex)
if vertex == endVertex: found = true
else: enqueue all adjacent unmarked vertices; mark them
while !queue.IsEmpty() and !found
if !found: write "Path does not exist"Worked example (slides 14, 17)
flowchart LR A((A)) --> B((B)) B --> C((C)) B --> D((D)) C --> E((E)) E --> A E --> D
- DFS from A: A B C E D or A B D C E (depends on the order neighbors are pushed).
- BFS from A: A B C D E or A B D C E.
Hands-on (slide 18)
flowchart TD n1((1)) --> n2((2)) n1 --> n3((3)) n2 --> n4((4)) n3 --> n6((6)) n4 --> n6 n4 --> n5((5)) n5 --> n7((7)) n5 --> n8((8))
BFS trace from 1
| Dequeued | Enqueued (newly marked) | Queue after |
|---|---|---|
| 1 | 2, 3 | 2 3 |
| 2 | 4 | 3 4 |
| 3 | 6 | 4 6 |
| 4 | 5 (6 already marked) | 6 5 |
| 6 | – | 5 |
| 5 | 7, 8 | 7 8 |
| 7 | – | 8 |
| 8 | – | ∅ |
BFS: 1 2 3 4 6 5 7 8 (or 1 3 2 6 4 5 8 7 with the other neighbor order).
DFS trace from 1 (stack, neighbors pushed in increasing order)
| Popped | Pushed | Stack after (top on the right) |
|---|---|---|
| 1 | 2, 3 | 2 3 |
| 3 | 6 | 2 6 |
| 6 | – | 2 |
| 2 | 4 | 4 |
| 4 | 5 (6 marked) | 5 |
| 5 | 7, 8 | 7 8 |
| 8 | – | 7 |
| 7 | – | ∅ |
DFS: 1 3 6 2 4 5 8 7 (or 1 2 4 5 7 8 6 3 with the recursive version / reverse push order).
⚠️ Several traversal orders are correct; they depend on the order in which neighbors are considered. Both traversals cost with adjacency lists.
4. Topological Sort
Definition – Topological sort
Applies to a directed acyclic graph: a numbering of the vertices such that every vertex’s descendants have larger numbers than the vertex. Several results are possible.
Application: order jobs/courses so that no prerequisite is violated.
Algorithm using a queue (vertices without predecessor)
Q = empty queue
while G not empty
if every vertex has a predecessor: "G contains a cycle"
else
s = a vertex without predecessor
G = G - s and the arcs leaving s
Q.enqueue(s)
cnt = 0
while Q not empty
s = Q.dequeue()
cnt = cnt + 1; order(s) = cntAlgorithm using a stack (vertices without successor)
P = empty stack
while G not empty
if every vertex has a successor: "G contains a cycle"
else
s = a vertex without successor
G = G - s and the arcs arriving at s
P.push(s)
cnt = 0
while P not empty
s = P.pop()
cnt = cnt + 1; order(s) = cnt⚠️ The slides write
order(s) = cnt + 1without updatingcnt, which numbers every vertex 1. Increment the counter each time.
Worked example
flowchart LR a((a)) --> b((b)) b --> c((c)) a --> d((d)) b --> e((e)) d --> e e --> c e --> f((f)) g((g)) --> d
Queue version trace
| Vertices without predecessor | Removed | Order so far |
|---|---|---|
| a, g | a | a |
| g, b | g | a g |
| b, d | d | a g d |
| b | b | a g d b |
| e | e | a g d b e |
| c, f | c | a g d b e c |
| f | f | a g d b e c f |
Possible solutions: (a) a, g, d, b, e, c, f or (b) a, b, g, d, e, f, c, …
5. Shortest Paths
Input: a graph with weights on the edges. Output: the edges forming the shortest path (in practice we compute distances).
Variants:
- shortest path between two named vertices;
- from a source to all other vertices (single-source);
- between all pairs of vertices.
Definitions
- = shortest distance from to .
- = weight of the edge from to ; if there is no such edge.
Dijkstra’s algorithm (single source)
Idea: process vertices in order of distance from the source. (Processing them in an arbitrary order fails: a vertex already processed might have a shorter path going through a later vertex.)
S = {v0} // set of fixed vertices
d[v0] = 0
for each v in V - {v0}: d[v] = w(v0, v)
while S != V
choose u in V - S with minimum d[u] // fix u
add u to S
for each v in V - S:
d[v] = min(d[v], d[u] + w(u, v))Worked example
flowchart LR A((A)) -->|10| B((B)) A -->|3| C((C)) A -->|20| D((D)) C -->|2| B B -->|5| D C -->|15| E((E)) D -->|11| E
| Step | A | B | C | D | E |
|---|---|---|---|---|---|
| Initial | 0 | ∞ | ∞ | ∞ | ∞ |
| fix A | 0 | 10 | 3 | 20 | ∞ |
| fix C | 0 | 5 (3+2) | 3 | 20 | 18 (3+15) |
| fix B | 0 | 5 | 3 | 10 (5+5) | 18 |
| fix D | 0 | 5 | 3 | 10 | 18 (10+11=21 > 18) |
| fix E | 0 | 5 | 3 | 10 | 18 |
Shortest distances from A: AB = 5, AC = 3, AD = 10, AE = 18.
Complexity
Implementation of “choose the min” (minVertex) | Cost |
|---|---|
| Scan the table of distances | |
| Min-heap (priority queue keyed by distance), updated on each edge |
void Dijkstra(Graph *G, int *D, int s) { // D[] initialized: D[s]=0, others ∞
for (int i = 0; i < G->n(); i++) {
int v = minVertex(G, D); // closest unvisited vertex
if (D[v] == INFINITY) return; // unreachable
G->setMark(v, VISITED);
for (int w = G->first(v); w < G->n(); w = G->next(v, w))
if (D[w] > D[v] + G->weight(v, w))
D[w] = D[v] + G->weight(v, w);
}
}⚠️ Dijkstra requires non-negative weights: once a vertex is fixed its distance is never revised.
6. All-Pairs Shortest Paths – Floyd’s Algorithm
Running Dijkstra times works, but Floyd’s algorithm is simpler; it works on directed or undirected weighted graphs.
Definition – -path
A path from to whose intermediate vertices all have indices less than . Floyd is dynamic programming: each path is computed once, using a matrix.
void Floyd(Graph *G) {
int D[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
D[i][j] = weight(i, j); // ∞ if no edge
for (int k = 0; k < n; k++) // allow k as intermediate
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (D[i][j] > D[i][k] + D[k][j])
D[i][j] = D[i][k] + D[k][j];
}Complexity: three nested loops → .
Worked example
Arcs: 1→3 (3), 2→1 (2), 3→2 (7), 3→4 (1), 4→1 (6).
flowchart LR v1((1)) -->|3| v3((3)) v2((2)) -->|2| v1 v3 -->|7| v2 v3 -->|1| v4((4)) v4 -->|6| v1
| Step (via vertex ) | Improvements |
|---|---|
| (via 1) | : ; : |
| (via 2) | : |
| (via 3) | : ; : ; : ; : |
| (via 4) | : |
⚠️ When updating with vertex , row and column never change in that step — use them to fill the rest of the matrix quickly: .
7. Subgraphs and Partial Graphs
Definition – Subgraph
is a subgraph of if and contains all edges of between vertices of :
(take some vertices and all their connecting edges).
Definition – Partial graph
is a partial graph of if (all vertices, some edges).
⚠️ Subgraph = remove vertices (and their edges); partial graph = remove edges only. A spanning tree is a partial graph.
8. Minimum Cost Spanning Trees (MST)
Definition – MST problem
Input: an undirected, connected, weighted graph . Output: a subset of edges that
- keeps all vertices connected, and
- has minimum total cost (sum of edge weights).
Uses: wiring network machines with the least cable; shortest road network linking several cities.
Prim’s algorithm
Grow one tree from an arbitrary vertex , always adding the cheapest edge leaving the tree.
V(T) = {r}; E(T) = ∅; N = V - {r}
while N not empty
take the shortest edge (u, v) with u ∈ V(T) and v ∈ N
add (u, v) to E(T); add v to V(T); remove v from NWorked example (start at 0)
flowchart TD v0((0)) ---|6| v1((1)) v0 ---|2| v3((3)) v0 ---|5| v2((2)) v1 ---|2| v4((4)) v1 ---|4| v6((6)) v3 ---|8| v4 v2 ---|5| v6 v2 ---|7| v5((5)) v4 ---|10| v5
| Step | Candidate edges leaving the tree | Chosen | |
|---|---|---|---|
| 1 | 0–1 (6), 0–3 (2), 0–2 (5) | 0–3 (2) | 0, 3 |
| 2 | 0–1 (6), 0–2 (5), 3–4 (8) | 0–2 (5) | 0, 2, 3 |
| 3 | 0–1 (6), 3–4 (8), 2–6 (5), 2–5 (7) | 2–6 (5) | 0, 2, 3, 6 |
| 4 | 0–1 (6), 3–4 (8), 2–5 (7), 6–1 (4) | 6–1 (4) | 0, 1, 2, 3, 6 |
| 5 | 1–4 (2), 3–4 (8), 2–5 (7) | 1–4 (2) | 0, 1, 2, 3, 4, 6 |
| 6 | 2–5 (7), 4–5 (10) | 2–5 (7) | all |
MST: {(0,3), (0,2), (2,6), (6,1), (1,4), (2,5)}, total cost 25.
Kruskal’s algorithm
Start with each vertex as its own tree ( trees). Process edges in increasing weight; accept an edge if it does not create a cycle (its endpoints are in different trees), merging the two trees.
A = {}
for each vertex v: MAKE_SET(v)
sort the edges of E by increasing weight
for each edge (u, v) in that order
if FIND_SET(u) != FIND_SET(v)
A = A ∪ {(u, v)}
UNION(u, v)
return AWorked example
flowchart TD A((A)) ---|7| C((C)) A ---|9| E((E)) B((B)) ---|5| C B ---|6| F((F)) C ---|1| D((D)) C ---|2| F D ---|2| F E ---|1| F
| Edge (sorted) | Trees before | Decision |
|---|---|---|
| C–D = 1 | {A} {B} {C} {D} {E} {F} | accept |
| E–F = 1 | {A} {B} {C,D} {E} {F} | accept |
| C–F = 2 | {A} {B} {C,D} {E,F} | accept |
| D–F = 2 | {A} {B} {C,D,E,F} | ✗ cycle |
| C–B = 5 | accept | |
| B–F = 6 | {A} {B,C,D,E,F} | ✗ cycle |
| C–A = 7 | accept | |
| A–E = 9 | {A,B,C,D,E,F} | ✗ cycle |
MST: {CD, EF, CF, CB, CA}, total cost 16 ( edges).
⚠️ In the slide pseudocode
UNION(u,v)is placed outside theif; it belongs inside it (calling it on the same set is harmless, but it’s the accepted edge that merges two trees). Also, when equal weights exist, Prim and Kruskal may return different trees with the same total cost.