0
$\begingroup$

I tried to implement Kruskal's minimal spanning tree algorithm and I found that the output is essentially a set of the edges... The output is not a tree at all. In my opinion, a tree can be represented by a parents array, and each node associates a key which is its parent. For a tree we need to know which node is its root at least I think. But the output of Kruskal's algorithm are just edges. How to fill this gap?

$\endgroup$
9
  • 1
    $\begingroup$ Before saying that the output is not a tree, it is worth looking up the definition of a tree! That being said, a minimal spanning tree certainly isn't a rooted tree, and it's not clear why you'd want it to be. $\endgroup$ Jun 6, 2023 at 5:32
  • $\begingroup$ You're probably confusing the computer science notion of a tree data structure with the graph theory notion of a tree (a graph with no cycles). $\endgroup$
    – Karl
    Jun 6, 2023 at 5:35
  • $\begingroup$ @Karl yes, a little, but in fact, they have close relations. If I can only define a tree by theory. How could I output it? To output it by an algorithm. It need be represented. $\endgroup$
    – cai jiu
    Jun 6, 2023 at 9:27
  • $\begingroup$ @MishaLavrov yes, but the problem is I need to represent it as an output of an algorithm. So when we are saying the output is a tree. What we are really talking about? $\endgroup$
    – cai jiu
    Jun 6, 2023 at 9:30
  • 1
    $\begingroup$ @caijiu The format users may hope for depends on the user - I think that's what all of us are seeing here! I think you have a legitimate question about representing the MST in a different format here. But phrasing it as "Kruskal's algorithm does not output a tree" is misleading; you're suggesting that there is a bug in the algorithm or the implementation, which is not accurate. $\endgroup$ Jun 6, 2023 at 13:33

1 Answer 1

2
$\begingroup$

The output of Kruskal's algorithm is a tree: it is an acyclic connected graph.

If you want to represent it by a "parents array", this can be done by a depth-first search through the tree. (An anything-first search will do, really; the point of having a tree is that there's only one way to traverse it.) Pick an arbitrary vertex to be the root of the tree. As you explore the rest of the tree by DFS, whenever you visit a vertex $v$, set $v$'s parent to be whichever vertex you visited it from.

It may be simpler to use Prim's algorithm instead. Prim's algorithm starts with a single vertex, and extends it to a larger and larger tree until the tree is a spanning tree. You can create the "parents array" representation of the tree as you go: whenever you identify a new cheapest edge $vw$, where $w$ is a vertex not previously part of the tree, set $w$'s parent to be $v$.

$\endgroup$
1
  • $\begingroup$ So this is the reason prim's algorithm is created. $\endgroup$
    – cai jiu
    Jun 19, 2023 at 9:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .