Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Minimal tree generators

  1. Jul 20, 2006 #1
    I was wondering,could someone explain me how do minimal tree generators work?
  2. jcsd
  3. Jul 20, 2006 #2
    Is this a Graph Theory or discrete math topic? Is it the minimal tree of the entire graph or connected to some node? mathworld.com

    either way its about having 2 sets...the set of Remaining Nodes A and the set of nodes you have visited B. The idea is to move nodes in A to B. The algorithm will always start off with the minimal edge(one with the smallest weight). From there you iterate till no more nodes can be connected to B or A is empty. The criteria for moving a node from A to B is simply the minimal edge that connects A to B.
  4. Jul 21, 2006 #3


    User Avatar
    Science Advisor

    Kruskal's algorithm works differently, starting with no edges and continuing to add the smallest-weight edge that does not form a cycle.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook