AS 2 Section D: Algorithms on Graphs

Welcome to Algorithms on Graphs! Graphs and networks are everywhere in modern life. From Google Maps calculating the quickest route to school, to engineers designing water piping systems with minimal cost, graph algorithms solve real-world logistical puzzles. In this chapter, you will learn systematic, step-by-step procedures (algorithms) that solve these problems with mathematical precision.

Don't worry if these algorithms seem mechanical or detailed at first. Once you master the simple rules behind each method, they become reliable and straightforward marks in your exam!

1. Essential Graph Terminology

Before jumping into the algorithms, let's review the fundamental building blocks of networks:

• Vertex (or Node): A point in a network representing an object or location, usually labelled with a letter like \(A\), \(B\), or \(C\).
• Edge (or Arc): A line or curve connecting two vertices. An edge connecting vertex \(A\) and vertex \(B\) is written as \(AB\).
• Weight: A numerical value assigned to an edge representing cost, distance, or time.
• Path: A sequence of connected edges where no vertex is visited more than once.
• Cycle (or Loop): A closed path that starts and ends at the exact same vertex without repeating any other vertex.
• Connected Graph: A graph where there is a path between every pair of vertices.
• Tree: A connected graph that contains no cycles.
• Spanning Tree: A tree that connects all vertices in the graph.
• Minimum Spanning Tree (MST): A spanning tree whose total sum of edge weights is as small as possible.

Important Formula to Remember:
If a connected graph has \(n\) vertices, any spanning tree connecting those vertices must contain exactly \(n - 1\) edges.

Key Takeaway: An MST links every vertex together with the minimum possible total weight without creating any loops or cycles.

2. Minimum Spanning Trees (MST)

Imagine you are tasked with laying broadband cables to link several towns together. You want every town connected to the network, but you want to lay the least amount of cable to save money. This is the Minimum Spanning Tree problem.

There are two primary algorithms you need to know: Kruskal's Algorithm and Prim's Algorithm.

Algorithm 1: Kruskal's Algorithm

Kruskal's algorithm is an "edge-first" approach. You always look for the cheapest available edge across the entire network, regardless of where it is.

Step-by-Step Method for Kruskal's:

Step 1: List all the edges in the graph in ascending order of weight (from smallest to largest).
Step 2: Select the edge with the lowest weight and add it to your tree.
Step 3: Move to the next smallest edge. Check whether adding it would create a cycle (a closed loop).
• If it does not form a cycle, add it to your tree.
• If it does form a cycle, reject it and cross it out.
Step 4: Repeat Step 3 until you have selected exactly \(n - 1\) edges (where \(n\) is the total number of vertices).
Step 5: Calculate the total weight of the MST by adding together the weights of all selected edges.

Memory Trick: Kruskal's = Keep sorting edges first!

Common Mistake to Avoid: In the exam, always state which edges you consider and explicitly write "rejected (forms a cycle)" if the question asks for a full trace of the algorithm.

Algorithm 2: Prim's Algorithm (Graphical Form)

Prim's algorithm is a "vertex-first" approach. Instead of picking edges from all over the graph, you start at a single vertex and grow one connected tree outward step-by-step.

Step-by-Step Method for Graphical Prim's:

Step 1: Choose any starting vertex (the exam question will usually specify one).
Step 2: Look at all the edges connected to the vertices currently in your tree.
Step 3: Choose the edge with the lowest weight that connects a vertex in your tree to a vertex not yet in your tree.
Step 4: Add this edge and new vertex to your tree.
Step 5: Repeat Steps 2 to 4 until all \(n\) vertices are included (giving \(n - 1\) edges in total).
Step 6: State the order in which edges were added and calculate the total weight.

Why cycles never occur in Prim's: Because you always choose an edge connecting a vertex inside the current tree to a vertex outside the current tree, it is impossible to form a cycle!

Algorithm 3: Prim's Algorithm in Matrix / Table Form

Often, a network is given as a distance matrix (a table of weights between vertices) rather than a visual diagram. Prim's algorithm works brilliantly on matrices.

Step-by-Step Method for Matrix Prim's:

Step 1: Choose a starting vertex (e.g., vertex \(A\)).
Step 2: Cross out the entire row for that vertex so you don't pick it again.
Step 3: Write the number 1 above the column of that starting vertex.
Step 4: Look down all numbered columns. Find the smallest non-deleted number in those columns.
Step 5: Circle this smallest value, and identify the row it is in (let's say row \(D\)). Edge \(AD\) is now selected.
Step 6: Cross out row \(D\), and number column \(D\) with the next integer (e.g., 2).
Step 7: Repeat Steps 4 to 6 across all numbered columns until every vertex has had its column numbered and row crossed out.

Key Takeaway: Kruskal's sorts all edges globally and avoids cycles. Prim's grows a single tree step-by-step from a chosen vertex. Both algorithms will always produce an MST with the same minimum total weight.

3. Shortest Path: Dijkstra's Algorithm

Dijkstra's Algorithm finds the shortest path from a single start vertex (source) to all other vertices in a network with non-negative weights. It is the foundation of modern GPS route planning!

At each vertex, we maintain three key pieces of information (often drawn in a small box):
1. Vertex Label: The name of the node (e.g., \(A\), \(B\), \(C\)).
2. Order of Labelling: The order in which this vertex's final distance is confirmed (\(1\text{st}\), \(2\text{nd}\), \(3\text{rd}\), etc.).
3. Permanent Label (Final Value): The absolute shortest distance from the start vertex to this vertex.
4. Working Values (Temporary Labels): Intermediate distances discovered as we explore different routes.

Step-by-Step Method for Dijkstra's Algorithm:

Step 1: Initialisation
• Set the start vertex permanent label to \(0\).
• Set its order of labelling to \(1\).
• The start vertex is now your current vertex.

Step 2: Update Working Values
• For your current vertex, look at all directly connected neighbours that do not yet have a permanent label.
• Calculate: \(\text{New Distance} = (\text{Permanent label of current vertex}) + (\text{Weight of connecting edge})\).
• Write this value in the working values section of that neighbouring vertex.
• Rule: If a neighbour already has a working value, only replace it if the newly calculated value is smaller.

Step 3: Select the Next Permanent Label
• Look across all unfinalised vertices in the entire graph.
• Find the vertex with the smallest temporary/working value.
• Make this smallest working value its permanent label.
• Assign it the next order of labelling (e.g., \(2, 3, 4, \dots\)).
• This vertex now becomes your new current vertex.

Step 4: Repeat
• Repeat Steps 2 and 3 until the destination vertex (or all vertices) receives a permanent label.

Finding the Shortest Path (Traceback Method)

Once Dijkstra's algorithm finishes, you know the length of the shortest path, but how do you find the exact route?

Work backwards from the destination vertex to the start:
An edge \(XY\) is on the shortest path if:

\((\text{Permanent label of } Y) - (\text{Weight of edge } XY) = (\text{Permanent label of } X)\)

By tracing backwards using this equation, you will form the exact sequence of vertices from finish to start.

Example Walkthrough of Traceback:
Suppose destination \(Z\) has a permanent label of \(18\), and edge \(YZ\) has weight \(4\).
\(18 - 4 = 14\).
If vertex \(Y\) has a permanent label of \(14\), then edge \(YZ\) is part of the shortest path!

Key Takeaway: Dijkstra's systematically locks in permanent labels from smallest to largest distance from the start node, guaranteeing the most direct route.

4. Quick Comparison & Summary

Kruskal's Algorithm:
• Purpose: Finds a Minimum Spanning Tree (MST).
• Method: Edge-focused; sort all edges by weight, add smallest edge that doesn't cause a cycle.
• Best used when: Working visually from a diagram with relatively few edges.

Prim's Algorithm:
• Purpose: Finds a Minimum Spanning Tree (MST).
• Method: Vertex-focused; grow a connected tree from a starting vertex by selecting the lowest-weight edge linking to an unvisited vertex.
• Best used when: The network is presented as a distance matrix / table.

Dijkstra's Algorithm:
• Purpose: Finds the Shortest Path from one source vertex to others.
• Method: Updates working values and assigns permanent labels in order of increasing distance from start.
• Remember: Only replaces working values if a strictly shorter path is found.

5. Top Exam Tips & Common Pitfalls

• Count your edges: If the graph has \(n\) vertices, check that your final MST has exactly \(n - 1\) edges.
• Show all working values in Dijkstra: Do not erase previous working values; cross them out neatly when updating them so the examiner can see your method.
• Order of labelling is critical: Ensure your order numbers (\(1, 2, 3, \dots\)) reflect the order in which vertices received their permanent labels, not when their working values were first written.
• State the final answer clearly: Always write down both the requested path/edges (e.g., \(AB, BC, CD\)) and the total numerical weight or length.