Prim, Kruskal Why? only undirected graph?

LogoWhy Can’t Prim’s or Kruskal’s Algorithms Be Used on a Directed Graph? | Baeldung on Computer ScienceBaeldung on Computer Science

In our example, there is just one MSA possible. That is s \rightarrow b \rightarrow a. But running Kruskal’s algorithm, we first of all select a \rightarrow b:

g4

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:

g5

This time the only possible MSA is s \rightarrow a \rightarrow b. Prim’s algorithm starts at a random node, in this case, s. It then takes the edge with the lowest edge connected to s, which is the node to b:

g6

Since the edge, s \rightarrow b is not contained in the only MSA that the following steps won’t generate an MSA for this example.

PreviousPrim vs DigkstraNextKruskal's Algorithm: undirected

Last updated