0

I have implemented the kruskal's algorithm in c++ in LEDA library. So, i stored in a linked list the edges that belong to a MST, and those that are not . So, i wanna make a checker program that checks if the edges are rigth, by checking if the MST cycle property is applied in my tree. I have to make this program with LEDA's dynamic trees. But my overall question is : If i have these edges: 

`u1-u2 
 u3-u5 
 u2-u3
  ...`

How can I order them so that they are continues , like:

u1-u2
u2-u3
u3-u5
user7337722
  • 1
  • 2
  • I'm not sure why you would need that. Call link on all of the tree edges (each edge has weight times -1 to change min to max), then for each non-tree edge uv, evert u and get the max (i.e., min times -1) cost from v to the root. – David Eisenstat Apr 07 '17 at 14:55
  • Hm.. im a bit confused :P can you explain me with an example pls ? – user7337722 Apr 07 '17 at 15:03
  • It'd be easier to have this conversation in the presence of some code. – David Eisenstat Apr 07 '17 at 15:04
  • My code is based on leda library . And its a bit hard to install it . I can give you some results of my code tho. Do you want ? – user7337722 Apr 07 '17 at 15:09
  • @user7337722 So you mean that a single element of the linked list contains both vertices like u1,u2? – Sumeet Apr 07 '17 at 18:19

0 Answers0