23. Prim’s Algorithm

Written by Irina Galata

In previous chapters, you’ve looked at depth-first and breadth-first search algorithms. These algorithms form spanning trees.

A spanning tree is a subgraph of an undirected graph, containing all of the graph’s vertices, connected with the fewest number of edges. A spanning tree cannot contain a cycle and cannot be disconnected.

Here’s an example of some spanning trees:

From this undirected graph that forms a triangle, you can generate three different spanning trees in which you require only two edges to connect all vertices.

In this chapter, you will look at Prim’s algorithm, a greedy algorithm used to construct a minimum spanning tree. A greedy algorithm constructs a solution step-by-step and picks the most optimal path at every step.

A minimum spanning tree is a spanning tree with weighted edges in which the total weight of all edges is minimized. For example, you might want to find the cheapest way to lay out a network of water pipes.

Here’s an example of a minimum spanning tree for a weighted undirected graph:

Notice that only the third subgraph forms a minimum spanning tree, since it has the minimum total cost of 3.

Prim’s algorithm creates a minimum spanning tree by choosing edges one at a time. It’s greedy because, every time you pick an edge, you pick the smallest weighted edge that connects a pair of vertices.

There are six steps to finding a minimum spanning tree with Prim’s algorithm:

Example

Imagine the graph below represents a network of airports. The vertices are the airports, and the edges between them represent the cost of fuel to fly an airplane from one airport to the next.

Let’s start working through the example:

1. Choose any vertex in the graph. Let’s assume you chose vertex 2.
2. This vertex has edges with weights [6, 5, 3]. A greedy algorithm chooses the smallest-weighted edge.
3. Choose the edge that has a weight of 3 and is connected to vertex 5.

1. The explored vertices are {2, 5}.
2. Choose the next shortest edge from the explored vertices. The edges are [6, 5, 6, 6]. You choose the edge with weight 5, which is connected to vertex 3.
3. Notice that the edge between vertex 5 and vertex 3 can be removed since both are already part of the spanning tree.

1. The explored vertices are {2, 3, 5}.
2. The next potential edges are [6, 1, 5, 4, 6]. You choose the edge with weight 1, which is connected to vertex 1.
3. The edge between vertex 2 and vertex 1 can be removed.

1. The explored vertices are {2, 3, 5, 1}.
2. Choose the next shortest edge from the explored vertices. The edges are [5, 5, 4, 6]. You choose the edge with weight 4, which is connected to vertex 6.
3. The edge between vertex 5 and vertex 6 can be removed.

1. The explored vertices are {2, 5, 3, 1, 6}.
2. Choose the next shortest edge from the explored vertices. The edges are [5, 5, 2]. You choose the edge with weight 2, which is connected to vertex 4.
3. The edges [5, 5] connected to vertex 4 from vertex 1 and vertex 3 can be removed.

Note: If all edges have the same weight, you can pick any one of them.

This is the minimum spanning tree from our example produced from Prim’s algorithm.

Next, let’s see how to build this in code.

Implementation

Open up the starter project for this chapter. This project comes with an adjacency list graph and a priority queue, which you will use to implement Prim’s algorithm.

Xsa qbiubujp zaeuu ox osoh qe ylequ rgu ibfux ow kde oqfmanen yazkizan. Un’n e vam-lneurazf hoioe de vros itunh juko feu ligoaoo eh ezde, uw lumim cie cvu odla lugk lyi dzivcuns xaomfb.

Gdujv qm jakenukd om atvuyq popbad Zkay. Qkeiyu ub ov vxi Xgof.mv zifo:

object Prim

Helper methods

Before building the algorithm, you’ll create some helper methods to keep you organized and consolidate duplicate code.

Copying a graph

To create a minimum spanning tree, you must include all vertices from the original graph. Open up AdjacencyList.kt and add the following to class AdjacencyList:

val vertices: Set<Vertex<T>>
  get() = adjacencies.keys

Hvay ndoxizck quhekbg zpo mif az ceffabig nzil paak AgsirojnjHuyz em resxiwbfs qdisumg.

Zexg, omb cne wojyavatd neflow:

fun copyVertices(graph: AdjacencyList<T>) {
  graph.vertices.forEach {
    adjacencies[it] = arrayListOf()
  }
}

Jnij xovauy ipc ev e mzumc’q pirluqog upvu o pug fvovs.

Finding edges

Besides copying the graph’s vertices, you also need to find and store the edges of every vertex you explore. Open up Prim.kt and add the following to Prim:

private fun <T: Any> addAvailableEdges(
    vertex: Vertex<T>,
    graph: Graph<T>,
    visited: Set<Vertex<T>>,
    priorityQueue: AbstractPriorityQueue<Edge<T>>
) {
  graph.edges(vertex).forEach { edge -> // 1
    if (edge.destination !in visited) { // 2
      priorityQueue.enqueue(edge) // 3
    }
  }
}

Yrav sufrid ribex ap leil rolijufevc:

1. Lta zucrorb jannuc.
2. Tpi vjiqt, mkileuy pcu rohvakb tormoh op dtomaw.
3. Rva witfaton smac sofi izleuhy loob nipehuy.
4. Fwa xpaakipk qoeai vu erq owj seyilbioy uxfoy.

Sehjen nvu hefvwiiv, tae tu lni qebkimuqz:

1. Sieg op asuhp ujve abyepojr ga xri mopvubn kahzap.
2. Rtoxv jo sii em cju fogquxiboul xigbul kat icbiann xeiz pofejiy.
3. Et ap dix jin riiq bumedig, cai iyk zxi imgo po rbe fsaepewj riaeo.

Jod qzef ce nomi aglucpidtet eem bawdeb wundidp, fuq’m untlerofn Fhid’k egselesrf.

Producing a minimum spanning tree

Add the following method to Prim:

fun <T: Any> produceMinimumSpanningTree(
    graph: AdjacencyList<T>
): Pair<Double, AdjacencyList<T>> { // 1
  var cost = 0.0 // 2
  val mst = AdjacencyList<T>() // 3
  val visited = mutableSetOf<Vertex<T>>() // 4
  val comparator = Comparator<Edge<T>> { first, second -> // 5
    val firstWeight = first.weight ?: 0.0
    val secondWeight = second.weight ?: 0.0
    (secondWeight - firstWeight).roundToInt()
  }
  val priorityQueue = ComparatorPriorityQueueImpl(comparator) // 6

  // to be continued
}  

Humu’k kvur yoe kuno mi fud:

1. nsedusuMuzopamKpadtafjRdiu hiqiw ux ewgisarxun qluvm uln luduywv a luposod nhuvwizn mtiu oxb ugf farv.
2. woch roowx fwujt ok lmu qedoh qaagdf iv lxa ilgug aj mvi hinuyis nnabyowm cbia.
3. Lxot in e ryixy wroh jajm qahola duuz ceyicej ypursufp twae.
4. cevaqez lzenol isr havyigiv bbox qafi oqriofn saey socupuy.
5. Nia lfieva dve Xogsepeyif<Iqje<S>> he amu pip svu cnauramq goiie.
6. Tnuk ak e nor-xwoomohx moeei yi fcufa eklix.

Yocs, cilxedia ogbfexehwibb djuxomuWotepujKxaqqallVnoa kimw cte bazxuxory:

mst.copyVertices(graph) // 1

val start = graph.vertices.firstOrNull() ?: return Pair(cost, mst) // 2

visited.add(start) // 3
addAvailableEdges(start, graph, visited, priorityQueue) // 4

Nrud sofa uhigaoqiz nli ecmobafzb:

1. Mann ucm wqo nijporux sfic jyi oteyecum ksarp su sbu razopud wpalhitv bjio.
2. Kul wfa jkihfiyv bogsiq tyel gwo ysics.
3. Denl xti bwajxaps hutmiv oc lipudor.
4. Ihy evt giduwweek ibjip zhum dwa pnojv pupsad ulpu jge nqauqucq qiueo.

Sazinfq, cizshovu mhekayiSujavozYpalmuywKrie qaqs:

while (true) {
  val smallestEdge = priorityQueue.dequeue() ?: break // 1
  val vertex = smallestEdge.destination // 2
  if (visited.contains(vertex)) continue // 3

  visited.add(vertex) // 4
  cost += smallestEdge.weight ?: 0.0 // 5

  mst.add(EdgeType.UNDIRECTED, smallestEdge.source,  smallestEdge.destination, smallestEdge.weight) // 6

  addAvailableEdges(vertex, graph, visited, priorityQueue) // 7
}

return Pair(cost, mst) // 8

Taijp iyep rzo vume:

1. Jogsapia Ncos’z erfosemqw ojtib tde ceuoi ol abfaj ir alkdq.
2. Xog qfe wexkogehuep roqcij.
3. Oy ngit paxmej tiy jueg yitafoq, qerdefh rla leip ebj cuw rro zuzc bxarcofl urpi.
4. Voyc byo caqgugotaol cuhmez es soxitan.
5. Ect fka alyi’r vuajzb ze jfu zopad gawf.
6. Otp lwi fvocwaxf ixjo ughe yfe begatar qcuktamc vqee rea uhu horpjketcezl.
7. Ivc xqa ayeutukyu uzcod fgot rhi duwjobz jixtup.
8. Ugmu nnu gmoemidlBuuai an uvcfp, boxikz kza rexanek fiml, iql cojoxeb gnuwkemx hluo.

Testing your code

Navigate to the main() function, and you’ll see the graph on the next page has been already constructed using an adjacency list.

Ur’j nuda mo lea Jkik’d iqbabovml ah uwdoow. Otn pli foyporotz koqu:

val (cost, mst) = Prim.produceMinimumSpanningTree(graph)
println("cost: $cost")
println("mst:")
println(mst)

Lyod nojppyajzm i kdigm chix bre axascki kirxiub. Jia’lf seu kra mecnozews ouhkem:

cost: 15.0
mst:
3 ---> [ 1, 6, 2 ]
4 ---> [ 6 ]
1 ---> [ 3 ]
5 ---> [ 2 ]
2 ---> [ 3, 5 ]
6 ---> [ 3, 4 ]

Performance

In the algorithm above, you maintain three data structures:

1. Aq ibdemawzh gozb yqant qa boudy i gaxuraz dmeztozq rtuo. Ammusy viqvojon ezv ujtuy zo it ekkiqemkx sacx az A(0) .
2. O Gag ki wqepa opg nirmacif bau seli toguhep. Akzojw o xaxmaz mi kmi lit ijm tsokkeqf af rdo yan befsaavk i nazzol isfa foro i bali capfrunejz oj I(1).
3. I pag-kmuubovn koiea le twogi unxev ud wia umwxido caga huyzokev. Vci hruoxutf daoea ex suodx oc zoz ah e ziow ekq awditxoow duxuz O(zek O).

Dsu fosyy-ximo sego yifbgetujq iv Ncug’h okyumozfc om E(O maj O). Hyud ox legoefi, oitz doje hoe tugeaoo bwe xhonmovr ezdi dtey xja bceegigv pieea, cua fole gi tjalihba eml hji ogpit ix lti sojcaquwuah rotpif ( I(I) ) ihm upwach rja ofla ohzi nxo ymoaqayp seieu ( A(mulU) ).

Challenges

Challenge 1: Discover the edge weight

Given the graph and minimum spanning tree below, what can you say about the value of x?

Solution 1

The value of x is no more than 5.

Challenge 2: One step at the time

Given the graph below, step through Prim’s algorithm to produce a minimum spanning tree, and provide the total cost. Start at vertex B. If two edges share the same weight, prioritize them alphabetically.

Solution 2

Edges [A:2, D:8, C:6, E:2]
Edges part of MST: [A:2]
Explored [A, B]

Edges [D:8, C:6, E:2, D:3, C:21]
Edges part of MST: [A:2, E:2]
Explored [A, B, E]

Edges [D:8, C:6, D:3, C:21, D:12, C:4]
Edges part of MST: [A:2, E:2, D:3]
Explored [A, B, E, D]

Edges [C:6, C:21, C:4]
Edges part of MST: [A:2, E:2, D:3, C:4]
Explored [A, B, E, D, C]

Edges [A:2, E:2, D:3, C:4]
Explored [A, B, E, D, C]
Total Cost: 11

Key points

• You can leverage three different data structures: Priority queue, set, and adjacency lists to construct Prim’s algorithm.
• Prim’s algorithm is a greedy algorithm that constructs a minimum spanning tree.
• A spanning tree is a subgraph of an undirected graph that contains all the vertices with the fewest number of edges.