If this is a homework assignment (and it sounds like one), please take a look at this.
Now, after you show some genuine effort, it would help writing your question in a little more detail, especially if you use some special definitions,
e.g. "light edge" (?)
P.S: I believe the solution requires some sort of formal proof, therefore Peter's answer probably doesn't mean anything - Kruskal's and Prim's are just 2 algorithms for finding a MST in a graph.
Last edited by Zachm; March 28th, 2009 at 03:36 PM.
A cut (S, V − S) of an undirected graph G = (V,E) is a partition of V .
An edge (u, v) crosses the cut iff one of ts endpoints is in S and the other is in V −S.
An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut.
P.S.-it is a homework assignment...
but the thing is that we hvnt been taught graphs as of yet in our Data Structure class. nonetheless, we are expected to submit it by the 4th of april. i tried studying it by myself, but couldnt understand most of the things. however, i managed to understand the above defintions.
i understand your policies regarding hw assignments, but i need your expert help urgently.