What is a network?

Think of a network as a map. The dots on the map are called vertices (or nodes) — these might represent towns, computers, or buildings. The lines connecting the dots are called edges (or arcs) — these represent a road, a cable, a flight route, whatever links two places together.

What makes a network special (compared to just any graph) is that every edge has a weight attached to it — a number representing something real, like distance in km, cost in £, or time in minutes. That's why a network is formally called a weighted graph.

Adjacency matrix vs. distance matrix

A matrix is just a table used to store all the connection information about a network in a grid, instead of drawing it out. There are two matrix types you need to tell apart:

Adjacency matrix

This tells you how many direct connections exist between each pair of vertices — it does care about weight, only about "is there a link, and if so how many?" Every vertex is listed as both a row heading and a column heading, so the matrix is always square.

• An entry of 0 means no direct connection between that pair of vertices.
• In a simple graph, entries are only ever 0 or 1.
• A loop (an edge that starts and ends at the same vertex) shows up on the leading diagonal (top-left to bottom-right). In an matrix this value is 2, because you can travel round the loop in two directions. In a matrix it's 1, because the loop only goes one way.
• An undirected graph's adjacency matrix is always symmetrical about the leading diagonal — the connection from A to B is identical to the connection from B to A.

Distance matrix

This is the one you'll use for MST problems. Instead of counting connections, each cell holds the weight of the edge between that pair of vertices (distance, cost, time — whatever the network measures). An empty cell means there's no direct edge between those two vertices at all.

A directed network's distance matrix will be symmetrical, because travelling A→B might cost something different from travelling B→A. When you're asked to draw a network from a distance matrix, check carefully: if the two "mirror" cells between a pair of vertices hold different numbers, you need two separate directed edges between them, each labelled with its own weight and arrow.

Spanning tree vs. minimum spanning tree

A spanning tree of a network is a subset of the edges that:

• connects every single vertex in the network (nothing gets left out), and
• contains no cycles (no loops — you can't go round in a circle and come back to where you started using only tree edges).

Because a tree with n vertices and no cycles always has exactly n − 1 edges, there's a really useful check built in: if you ever end up with more than n − 1 edges, you've made a mistake (you've allowed a cycle in). If you end up with fewer, you haven't finished — some vertex still isn't connected.

There are usually possible spanning trees for a given network. The minimum spanning tree (MST) is simply the one out of all those possibilities whose edges add up to the smallest total weight.

How it works

Kruskal's algorithm takes a completely different approach from "building outward" — instead, it looks at every edge in the whole network at once, sorted from cheapest to most expensive, and just keeps grabbing the next cheapest one . "Safe" means it doesn't close a loop with the edges you've already picked.

The steps

1. Step 1: List every edge in the network in order of increasing weight (cheapest first).
2. Step 2: Select the edge of least weight. Add it to your tree.
3. Step 3: Look at the next-cheapest edge that you haven't already considered.
   • If adding it would create a cycle with edges already in your tree → reject it.
   • Otherwise → add it to your tree.
4. Step 4: Repeat Step 3 until all vertices are connected (i.e. until you have n − 1 edges).
5. Step 5: List the edges of your finished MST in the order you added them — this is what examiners want to see as "working."

Worked example

Consider this network with vertices A, B, C, D, E, F, G, H and these edges: AB(4), AD(9), AE(11), BC(6), BF(7), CD(8), CG(15), DH(2), EF(5), EH(1), FG(5), GH(6).

Prim's algorithm using a graph

Where Kruskal's algorithm scans the network for the cheapest safe edge anywhere, Prim's algorithm is much more local: it starts at one vertex and grows the tree outward like a plant, always reaching for the cheapest edge that's directly touching the tree it's already built.

The steps (using a graph)

1. Step 1: Start at any vertex and choose the edge of least weight that's connected to it.
2. Step 2: Choose the edge of least weight that is incident (connected) to any vertex already in the tree, but which connects to a vertex not yet in the tree. (If there's a tie for cheapest, either can be picked.)
3. Step 3: Repeat Step 2 until every vertex has been added.

Worked example (using a graph)

Network with vertices A, B, C, D, E and edges: AB(15), AC(22), AD(18), AE(25), BC(13), BD(17), BE(24), CD(30), CE(12), DE(21). Starting at A:

Prim's algorithm using a matrix

This is the version you'll use when the network is given as a table rather than a drawing — and it's the method examiners often expect for matrix-based questions, since Kruskal's is awkward to apply directly from a table.

The steps (using a matrix)

1. Step 1: Pick any starting vertex. Cross out the values in the column for that vertex, and label its row with the number 1.
2. Step 2: Circle the lowest value in any cell along that labelled row. Add that edge to your tree. Cross out the remaining values in the column of the cell you just circled.
3. Step 3: Label the row that corresponds to the same vertex as the column you just crossed out, with the next number (2, then 3, and so on).
4. Step 4: Circle the lowest value in any cell along any labelled row (there may now be several labelled rows to check). Add the edge, cross out that column.
5. Step 5: Repeat Steps 3–4 until every vertex has been added to the tree.

Worked example

Distance matrix for A–E (same network as above), starting at A:

Choosing the right algorithm

Both algorithms are guaranteed to find minimum spanning tree for the network — they might pick edges in a different order, and even choose slightly different tied-weight edges, but the total weight of the finished tree will always come out the same.

• Prim's algorithm can be used on a network given as a graph or as a matrix. If your question gives you a table/matrix, Prim's is the natural choice.
• Kruskal's algorithm works best when the network is given as a graph, or as a straightforward list of edges. If you only have a matrix, you'd normally sketch the graph first before applying Kruskal's.
• Kruskal's lets you add arcs in any order across the whole network — the tree can be split into separate unconnected pieces mid-algorithm. Prim's always builds one connected blob from the start.
• Prim's is sometimes considered more efficient, because it doesn't require sorting every edge up front, and it doesn't need an explicit cycle-check at each step (the "cross out the column" trick handles that automatically).