1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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