Prim, Kruskal Why? only undirected graph?
In our example, there is just one MSA possible. That is 
. But running Kruskal’s algorithm, we first of all select 
:
Since this edge is not contained in our MSA it is impossible to construct one from the Kruskal algorithm in this example.
3.2. Prim
For the Prim algorithm, we have a similar setup:
This time the only possible MSA is 
. Prim’s algorithm starts at a random node, in this case, 
. It then takes the edge with the lowest edge connected to , which is the node to 
:
Since the edge, 
is not contained in the only MSA that the following steps won’t generate an MSA for this example.
Last updated
