Algorithms on graphs
Edexcel International A-Level MathematicsΒ· D1 Β§2.1, D1 Β§2.2 (2018 Specification Issue 3)Β· 25 min read
1. Kruskal's Algorithm for Minimum Spanning Treesβ β ββββ± 5 min
β Calculator OK
Kruskal's Algorithm
Greedy algorithm that constructs a minimum spanning tree (MST) by sorting all edges by weight ascending, then adding edges one by one, skipping any edge that would create a cycle, until all vertices are connected.
Example:
For a graph with 5 vertices, Kruskal's will select 4 edges for the MST with no cycles.
Find the MST and its total weight for the following graph: Vertices A, B, C, D. Edges: AB=3, AC=5, BC=1, BD=4, CD=2.
- 1
Step 1: Sort all edges by weight ascending: BC (1), CD (2), AB (3), BD (4), AC (5)
- 2
Step 2: Add BC (weight 1): vertices B and C are connected, no cycle formed
- 3
Step 3: Add CD (weight 2): vertices B, C, D are connected, no cycle formed
- 4
Step 4: Add AB (weight 3): all 4 vertices are connected, stop
- 5
Step 5: Total MST weight = 1 + 2 + 3 = 6, selected edges: BC, CD, AB
2. Prim's Algorithm for Minimum Spanning Treesβ β β βββ± 7 min
β Calculator OK
Prim's Algorithm
Greedy algorithm that builds an MST starting from any chosen vertex, adding the smallest weight edge that connects a vertex in the existing tree to a vertex outside the tree, until all vertices are included. Can be applied directly to a network diagram or an adjacency matrix.
Example:
For a 4-vertex graph, Prim's will add 3 edges to form a valid MST, with no cycles.
Use the matrix version of Prim's starting at vertex A to find the MST for the adjacency matrix below: Rows/columns A,B,C,D. A: -,3,5,-; B:3,-,1,4; C:5,1,-,2; D:-,4,2,-.
- 1
Step 1: Start at A, cross out row A. The smallest value in uncrossed rows for columns not added is 3 (edge AB). Add AB, weight 3
- 2
Step 2: Cross out row B. The smallest value in uncrossed rows for columns not added is 1 (edge BC). Add BC, weight 1
- 3
Step 3: Cross out row C. The smallest value in uncrossed rows for columns not added is 2 (edge CD). Add CD, weight 2
- 4
Step 4: All 4 vertices are added, total MST weight = 3 + 1 + 2 = 6, matching the Kruskal's result
3. Converting Between Networks and Adjacency Matricesβ β ββββ± 4 min
β Calculator OK
Edexcel often asks you to convert a graph diagram to an adjacency matrix, or interpret a matrix to draw a network, before applying Prim's algorithm. For undirected graphs, the matrix is symmetric, with dashes or β on the diagonal (no edges from a vertex to itself) and dashes or β where no edge exists between two vertices.
Convert the 4-vertex network from the earlier Kruskal's example to an adjacency matrix.
- 1
Step 1: Label rows and columns A, B, C, D in the same order
- 2
Step 2: Fill diagonal entries with "-" as there are no self-edges
- 3
Step 3: Enter edge weights for each pair: AB=3, AC=5, BC=1, BD=4, CD=2
- 4
Step 4: Fill remaining entries (AD) with "-" as no edge exists between A and D. The resulting matrix matches the one used in the Prim's matrix example.
4. Dijkstra's Algorithm for Shortest Pathβ β β β ββ± 8 min
β Calculator OK
Dijkstra's Algorithm
Greedy algorithm that finds the shortest path from a single start vertex to all other vertices in a graph with non-negative edge weights. Uses temporary labels for tentative distances, which are updated to permanent labels once the shortest distance to that vertex is confirmed.
Example:
Dijkstra's can be used to find the shortest route between two towns on a map where edges represent roads and weights represent travel time.
Find the shortest path from A to D using Dijkstra's algorithm on the graph: A connected to B (3), A connected to C (5); B connected to C (1), B connected to D (4); C connected to D (2).
- 1
Step 1: Label A with permanent distance 0. Temporary labels: B=3, C=5, D=β
- 2
Step 2: Select the smallest temporary label (B=3), mark as permanent. Update adjacent vertices: C = min(5, 3+1=4) β 4; D = min(β, 3+4=7) β7
- 3
Step 3: Select the smallest temporary label (C=4), mark as permanent. Update adjacent vertex D = min(7, 4+2=6) β6
- 4
Step 4: Select the smallest temporary label (D=6), mark as permanent. All vertices processed. Shortest path: AβBβCβD, total weight 6.
5. Common Pitfalls
Wrong move:
Adding edges that create cycles in Kruskal's algorithm
Why:
Edges are sorted by weight, but you must check if the two vertices of the edge are already connected. Adding a cycle edge increases total weight unnecessarily and gives an invalid MST.
Correct move:
After sorting edges, check if the two endpoints of each edge are in separate connected components before adding it. Explicitly note skipped edges in your working for the examiner.
Wrong move:
Forgetting to cross out rows when using matrix Prim's algorithm
Why:
If you do not cross out rows of vertices already added to the tree, you may accidentally select an edge connecting two vertices already in the tree, creating a cycle.
Correct move:
Every time you add a vertex to your MST, immediately cross out its row in the adjacency matrix before selecting the next smallest edge.
Wrong move:
Stopping Dijkstra's algorithm as soon as you label the end vertex, before confirming it is permanent
Why:
A temporary label may be updated to a smaller value later if a shorter path is found via another vertex.
Correct move:
Only stop Dijkstra's when the target vertex has a permanent label, or all vertices are processed.
Wrong move:
Using negative edge weights with Dijkstra's algorithm
Why:
Dijkstra's is not designed for negative weights, and will return incorrect shortest path results if negative edges are present.
Correct move:
Confirm all edge weights are non-negative before applying Dijkstra's, as required for all Edexcel D1 exam questions.
Wrong move:
Failing to list the order of edge/vertex selection in your answer
Why:
Edexcel awards method marks for correct ordering, even if you make a small arithmetic error later. Skipping this step loses easy marks.
Correct move:
Always write the ordered list of edges (for Kruskal/Prim) or permanent labels (for Dijkstra) clearly, in the order you selected them.
6. Quick Reference Cheatsheet
Algorithm | Use Case | Key Steps | Exam Requirement |
|---|---|---|---|
Kruskal's | Find MST |
| List edges in selection order, note skipped cycle edges |
Prim's (Network) | Find MST |
| Show order of vertex/edge addition |
Prim's (Matrix) | Find MST from adjacency matrix |
| Show crossed out rows for each step |
Dijkstra's | Find shortest path between two vertices |
| Show all temporary/permanent labels, state final path and weight |
7. Frequently Asked
Do I have to show all working for graph algorithms in the exam?
Yes, Edexcel awards marks for every step: ordered edge/vertex selection, labeling of temporary/permanent labels for Dijkstra's, and clear checks for cycles in Kruskal's. Skipping steps will cost you marks even if your final answer is correct.
Can I use the network version of Prim's instead of the matrix version if both are provided?
Yes, you may use either version of Prim's unless the question explicitly specifies to use the matrix method. Both produce the same MST if executed correctly.
Going deeper
What's Next
Now that you have mastered core graph algorithms for Edexcel IAL D1, you are ready to move to more advanced decision mathematics topics. Next, you will learn route inspection and travelling salesman problems, which build on the graph logic you have practiced here. You should also practice past paper questions on these algorithms to refine your speed and accuracy, as they appear in almost every D1 exam paper, accounting for 15-25% of total marks per paper. Make sure you follow Edexcel's required working format to avoid losing method marks.