8000 Prims mst + script · DontFearAlgorithms/Algorithms-1@80e449c · GitHub
[go: up one dir, main page]
Skip to content

Commit 80e449c

Browse files
williamfisetwilliamfiset
committed
Prims mst + script
1 parent 80cfdf8 commit 80e449c

File tree

2 files changed

+104
-1
lines changed

2 files changed

+104
-1
lines changed

‎slides/graphtheory/prims_mst.key

112 KB
Binary file not shown.

‎slides/graphtheory/prims_mst_script.txt

Lines changed: 104 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -443,19 +443,122 @@ From this point on I will let the animation play.
443443
...
444444

445445
@164.
446-
And that's
446+
Alright, that's the algorithm, and the MST are the edges in green.
447447

448+
@165.
449+
If we collapse the graph back into the undirected edge view it becomes clear
450+
which edges are included in the MST.
451+
452+
@166.
453+
You can also get the MST cost by adding all the edges of the spanning tree for
454+
a total cost of 9.
455+
456+
@167.
457+
Let's have a look at some pseudo code for the eager implementation of Prim's
458+
MST algorithm. You'll notice that it's almost identical to the lazy version
459+
except for a few key details which I will highlight.
460+
461+
@168.
462+
First is n, this is still the number of nodes in the graph.
463+
464+
@169.
465+
ipq represents that we're using an indexed priority queue instead of a
466+
traditional PQ to store (node index, edge object) pairs. Edge objects are still
467+
represented as {start node, end node, edge cost} triplets and the node index is
468+
simply an integer.
469+
470+
@170.
471+
g is once again our graph adjacency list of weighted edges. In g, every
472+
undirected edge is represented as two directed edges.
473+
474+
@171.
475+
And lastly is a visited boolean array of size n which tracks whether node i has
476+
been visited or not.
477+
478+
@172.
479+
Now let's look at the actual algorithm for eager Prim's.
480+
481+
@173.
482+
In this first block I define a few more variables we'll need:
483+
'm' the number of expected edges in the MST.
484+
'edgeCount' the number of edges we have currently included in the MST. This
485+
variable is used to make sure the tree spans the whole graph.
486+
'mstCost' tracks the total cost of the MST
487+
and finally, 'mstEdges' is an array which holds edges which we have included in
488+
the MST.
489+
490+
@174.
491+
Then I call the relaxEdgesAtNode method passing the start node as an argument.
492+
Let's have a look inside the relaxEdgesAtNode method to understand what's
493+
happening.
494+
495+
@175.
496+
Here we are. You'll notice that this method takes a single argument which is the
497+
current node we care about.
498+
499+
@176.
500+
The first thing we do is mark the current node as visited so that we don't visit
501+
it again in the future.
502+
503+
@177.
504+
Then I reach into our graph adjacency list and get all edges going outwards from
505+
the current node.
506+
507+
@178.
508+
As we enter the loop and start iterating over all the outgoing edges the first
509+
thing I do inside the loop is grab a reference to the destination node index,
510+
this is the node the edge is pointing at.
511+
512+
@179.
513+
Next, skip edges which point at already visited nodes.
514+
515+
@180.
516+
Now here's the bit where we actually relax the edge. First I check if the IPQ
517+
contains the key with the value of the destination node.
448518

519+
@181.
520+
If it doesn't then add the edge to the IPQ for the first time.
449521

522+
@182.
523+
Otherwise, try and improve the cheapest edge at destNodeIndex with the current
524+
edge in the IPQ.
450525

526+
@183. <nothing>
451527

528+
@184.
529+
We're back inside the main method.
452530

531+
@185.
532+
Next up, keeping looping while the IPQ is not empty and the MST is not complete.
453533

534+
@186.
535+
After, extract the next best (node index, edge object) pair from the IPQ based
536+
on minimum edge cost.
454537

538+
@187.
539+
Include the selected edge as part of the MST and sum over the edge cost.
455540

541+
@188.
542+
Lastly, relax all the edges of the new current node and repeat until the
543+
loop breaks.
456544

545+
@189.
546+
Outside the main loop, check if we have successfully created a spanning tree,
547+
this might not be the case if some of the nodes are unreachable. But assuming
548+
that's not the case return the MST cost and the edges which make up the spanning
549+
tree.
457550

551+
@190.
552+
And that concludes the pseudo code for Prim's algorithm, thank you so much for
553+
watching! Implementation source code and slides can be found at github.com slash
554+
williamfiset slash algorithms.
555+
There should be a link in the description below. Please give this video a thumbs
556+
up if you learned something and subscribe for more mathematics and computer
557+
science videos.
458558

559+
@191.
560+
Next video we'll be looking at some source code for the eager implementation of
561+
Prim's MST algorithm, so stick around if you want to see more.
459562

460563

461564

0 commit comments

Comments
 (0)
0