Graph Algorithms

Graphs and how computers store them

A graph has vertices (nodes) and edges (links). Edges may be directed (one-way arrows) and may have weights (distance, cost, time or capacity).

• Adjacency matrix: a table where row i, column j holds the weight of edge i→j (or 0). Fast to check one edge; uses n² space.
• Adjacency list: each vertex keeps a list of its neighbours. Saves space when the graph has few edges (sparse).

The degree of a vertex is the number of edges at it. In the 3D graph, C has degree 4.

Traversals: breadth-first and depth-first

Breadth-first search (BFS)

1. Put the start vertex in a queue and mark it visited.
2. Take the vertex at the front of the queue.
3. Add each unvisited neighbour to the back of the queue and mark it.
4. Repeat until the queue is empty.

BFS finds the path with the fewest edges in an unweighted graph. Uses: shortest route in a maze, friends of friends, web crawlers.

Depth-first search (DFS)

1. Visit the start vertex and mark it.
2. Go to an unvisited neighbour and repeat from there (push onto a stack, or use recursion).
3. At a dead end, backtrack (pop) to the last vertex with an unvisited neighbour.

Uses: solving mazes and puzzles, finding cycles, checking whether a graph is connected, topological sort of tasks.

Both take time proportional to V + E (vertices + edges) with an adjacency list.

Tree traversals: pre-order, in-order, post-order

A tree is a connected graph with no cycles. For a binary tree, DFS can visit the root at three different moments:

• Pre-order: root, left, right – used to copy a tree or write prefix (Polish) notation.
• In-order: left, root, right – gives the values of a binary search tree in sorted order.
• Post-order: left, right, root – used to delete a tree or evaluate postfix (Reverse Polish) expressions.

Example: tree with root 8, left child 3 (children 1 and 6), right child 10. Pre-order: 8, 3, 1, 6, 10. In-order: 1, 3, 6, 8, 10. Post-order: 1, 6, 3, 10, 8.

Dijkstra's shortest-path algorithm

1. Give the start vertex distance 0 and all others ∞.
2. Pick the unfixed vertex with the smallest distance and fix it (its distance is now final).
3. For each neighbour, if (fixed distance + edge weight) is smaller than its current distance, update it and note where it came from.
4. Repeat until all vertices are fixed. Trace back the "came from" notes to get the route.

In the 3D graph from A: A = 0, C = 2, B = 3 (via C, not the direct road of 4), D = 8, E = 10, F = 13. Dijkstra only works when no weight is negative. With a priority queue it runs in about (V + E) log V time.

Minimum spanning trees, route inspection and the travelling salesperson

Minimum spanning tree (MST)

A spanning tree joins all V vertices with V − 1 edges and no cycles. The MST has the smallest total weight.

• Kruskal: sort edges by weight; add each edge unless it makes a cycle.
• Prim: start anywhere; repeatedly add the cheapest edge joining the tree to a new vertex (easy to do on a distance table).

In the 3D graph: BC 1, AC 2, DE 2, EF 3, BD 5 → total 13 km (AB 4 is rejected: it would make a cycle).

Route inspection (Chinese postman)

Find the shortest closed route that uses every edge at least once. If all degrees are even, the answer is the total weight. Otherwise pair up the odd-degree vertices and add the shortest paths between the pairs. In the 3D graph, B and E are odd; total weight 41 + shortest B–E path 7 = 48 km.

Travelling salesperson (TSP)

Find the shortest tour visiting every vertex once and returning. No fast exact method is known, so we find bounds:

• Upper bound: the nearest-neighbour tour (always go to the nearest unvisited vertex).
• Lower bound: delete one vertex, find the MST of the rest, then add the two shortest edges from the deleted vertex.

The best tour lies between the two bounds.

Network flows: max flow and min cut

A flow network is a directed graph where each arc has a capacity (most it can carry), like pipes or roads. Flow leaves a source S and reaches a sink T. At every other vertex, flow in = flow out.

• A cut splits the vertices into a part with S and a part with T. Its capacity is the sum of capacities of arcs going from the S side to the T side.
• Max-flow min-cut theorem: the largest possible flow equals the capacity of the smallest cut.
• Flow augmentation: start with any valid flow, find a path from S to T with spare capacity (it may push back along an arc already carrying flow), add flow along it, repeat until none is left.
• Several sources or sinks? Add a supersource joined to each source, and a supersink, with unlimited capacity.
• An arc may also have a lower capacity (it must carry at least that much). A flow is feasible only if every arc stays between its lower and upper capacity.

Example: S→A 4, S→B 3, A→B 2, A→T 3, B→T 4. Send 3 along S-A-T, 3 along S-B-T, 1 along S-A-B-T: flow 7. The cut {S} | {A, B, T} has capacity 4 + 3 = 7, so 7 is the maximum.

Try it: be the algorithm

Draw 6 dots for houses on your street and join them with lines; write distances in steps. Run Dijkstra by hand from your house using a table, then check with the free-play step (use start A). Then find the cheapest way to connect every house with cable (MST).

Key formulas and definitions

• BFS uses a queue (first in, first out); DFS uses a stack (last in, first out) or recursion
• Dijkstra update: if d(v) + w(v,u) < d(u) then d(u) = d(v) + w(v,u)
• A spanning tree on V vertices has V − 1 edges
• Route inspection = total weight + shortest paths pairing the odd vertices
• Max flow = capacity of the minimum cut

Worked examples

Common mistakes

• Using a stack for BFS or a queue for DFS. BFS needs a queue; DFS needs a stack.
• Fixing a vertex in Dijkstra as soon as it gets a label. Only the smallest unfixed label is fixed each time.
• In Kruskal, adding an edge that forms a cycle just because it is cheap.
• Counting a cut's capacity using arcs that go from the T side back to the S side. Only S-side → T-side arcs count.