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