| Share this post! | Vote this! |
|
The idea behind minimum spanning trees is simple: given a graph with
weighted edges, find a tree of edges with the minimum total weight. What is a
spanning tree? A graph that satisfies these three properties: connected,
acyclic, and consisting of |V| - 1 edges. (In fact, any two of the three
conditions imply the third condition.) What this means in practice is that a
spanning tree is a collection of edges that connect any two nodes via a single
path. It's probably easiest to understand a tree using the definition that a
tree is both connected and acyclic; think about binary trees--every node in
the tree is reachable, so it's connected, and there are no cycles because you
can't go back up the tree. more...
0 comments:
Post a Comment