Graph Algorithms — Visual & Coloured

How to read these pictures

This is the visual companion to the graph-algorithms course. Each algorithm is shown on a concrete example graph that is drawn and coloured by its result:

• Node colour encodes the answer — a BFS distance layer, a connected component, a prerequisite level, a colour class, a shortest-distance rank.
• Green edges mark a tree the algorithm builds (shortest-path tree, MST).
• Red edges mark a problem (a conflict, or a negative weight).
• Numbers on edges are weights.

A short legend sits above every drawing.

1. BFS — coloured by distance

From Ana, breadth-first search colours every person by how many introductions away they are. The tree of green edges is the shortest chain to each person.

Green edges = the BFS shortest-path tree.

Adjacent layers always differ by one — that is exactly why BFS gives shortest unweighted distances.

2. DFS — coloured by connected component

Depth-first search started from each unvisited vertex paints one entire connected component before moving on. Here two separate clusters get two colours.

DFS from any unvisited vertex paints one whole connected component.

3. Topological sort — the prerequisite DAG, coloured by depth

The Discrete-Mathematics courses as a directed acyclic graph. Arrows point from a course to the one it unlocks; colour is the prerequisite depth (how many courses must come before it). Reading the colours left to right gives a valid study order.

4. Bipartite check — a clean two-colouring

Six conflicting sessions split perfectly between two rooms: every edge joins a blue vertex to a yellow one, so the conflict graph is bipartite.

…and when it fails

A triangle is an odd cycle: after colouring two vertices, the third clashes — no two-room split exists.

The red edge joins two vertices the algorithm was forced to give the same colour ⇒ not bipartite.

5. Dijkstra — coloured by shortest distance

Travel-time map from S. Nodes are shaded by their final distance rank (nearest → farthest); the green edges form the shortest-path tree the algorithm settles.

Node colour = rank of final distance from S (S=0, A=5, B=2, C=9, D=7, E=10). Green = shortest-path tree.

6. Bellman–Ford — the negative edge in red

The same shortest-path idea, but one edge has a negative weight (red). Dijkstra would mis-handle it; Bellman–Ford relaxes every edge repeatedly and still finds the correct distances.

Red arrow = the negative edge A→C = −4 (Dijkstra could not handle it). Final distances: S=0, A=6, B=4, C=2, D=1.

7. Minimum Spanning Tree — chosen edges in green

Connecting five towns at least cost. Every possible link is drawn with its price; the thick green links are the ones Kruskal/Prim keep — the cheapest network with no redundant loop.

8. Greedy colouring — when the order matters

The "crown" timetable graph is 2-colourable (two exam slots suffice). A bad visiting order forces greedy into a third slot:

A good order (one whole side first) recovers the optimal two slots — same graph, fewer colours:

Same vertices, same edges — only the order changed. Greedy colouring is fast but not guaranteed minimal.

9. Eulerian graphs — use every edge exactly once

Rule. A connected graph has an Eulerian circuit (closed) exactly when every vertex has even degree.

Degrees A:2, B:2, C:4, D:2, E:2 — all even ✓. The orange numbers give one Eulerian circuit, edge by edge: A → C → E → D → C → B → A (start = end).

9a. Eulerian path — and when it is impossible

Rule. A connected graph has an Eulerian path (open) exactly when it has exactly two odd-degree vertices — and the path must start at one and finish at the other.

The two odd vertices are C, D. One stroke does it: C → E → D → A → B → C → D.

When it is impossible — the Seven Bridges of Königsberg

Königsberg's four land masses each touched an odd number of bridges. With four odd-degree vertices, no Euler path or circuit exists — Euler's 1736 proof that the famous walk is impossible, and the birth of graph theory.

All four vertices have odd degree (N:3, E:3, S:3, W:3) ⇒ more than two odd vertices ⇒ no Eulerian path.

10. Hamiltonian graphs — visit every vertex exactly once

A Hamiltonian cycle passes through every vertex exactly once and returns to the start. Here the outer hexagon is one such cycle (green); the diagonals are extra roads it does not need.

Visiting order: 1 → 2 → 3 → 4 → 5 → 6 → 1 — every city once, back to the start.

When none exists

Vertex S below is a dead-end (degree 1). You can enter it but never leave to continue a tour, so no Hamiltonian cycle exists. Unlike the Eulerian case there is no simple degree rule — deciding Hamiltonicity is NP-complete in general.

Eulerian vs Hamiltonian — the one-line difference

Colour key — what each colour meant

Notes By Pr. El Hadiq Zouhair