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.

KindDefinition
Undirected graphedges have no direction
Directed graph (digraph)vertices are linked by arcs (oriented edges) from an origin to a destination
Weighted grapheach 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

TermDefinition
Adjacent verticesconnected by an edge
Pathsequence with an edge from to ; its length is
Simple pathall vertices distinct
Cyclepath of length ≥ 3 connecting to itself
Simple cyclesimple path except that first = last vertex

Definition – Complete graph

An edge between every pair of vertices.

Graph with verticesNumber 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.

01234
011
11
21
31
41

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:

01234
011
1111
211
311
4111

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 matrixAdjacency list
Good fordense graphs, sparse graphs,
Memory
Fast operationtest if two vertices are connectedlist 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

DequeuedEnqueued (newly marked)Queue after
12, 32 3
243 4
364 6
45 (6 already marked)6 5
6–5
57, 87 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)

PoppedPushedStack after (top on the right)
12, 32 3
362 6
6–2
244
45 (6 marked)5
57, 87 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) = cnt

Algorithm 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 + 1 without updating cnt, 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 predecessorRemovedOrder so far
a, gaa
g, bga g
b, dda g d
bba g d b
eea g d b e
c, fca g d b e c
ffa 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
StepABCDE
Initial0∞∞∞∞
fix A010320∞
fix C05 (3+2)32018 (3+15)
fix B05310 (5+5)18
fix D0531018 (10+11=21 > 18)
fix E0531018

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

  1. keeps all vertices connected, and
  2. 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 N

Worked 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
StepCandidate edges leaving the treeChosen
10–1 (6), 0–3 (2), 0–2 (5)0–3 (2)0, 3
20–1 (6), 0–2 (5), 3–4 (8)0–2 (5)0, 2, 3
30–1 (6), 3–4 (8), 2–6 (5), 2–5 (7)2–6 (5)0, 2, 3, 6
40–1 (6), 3–4 (8), 2–5 (7), 6–1 (4)6–1 (4)0, 1, 2, 3, 6
51–4 (2), 3–4 (8), 2–5 (7)1–4 (2)0, 1, 2, 3, 4, 6
62–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 A

Worked 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 beforeDecision
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 = 5accept
B–F = 6{A} {B,C,D,E,F}✗ cycle
C–A = 7accept
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 the if; 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.