Thread: Prim's and Kruskal's minimum cost spanning tree

  1. #1
    Registered User gaurav9991's Avatar
    Join Date
    Oct 2010
    Location
    Pune, Maharashtra, India
    Posts
    69

    Prim's and Kruskal's minimum cost spanning tree

    is it possible that the minimum cost of spanning of a weighted graph is different by Kruskal's algorithm and by Prim's algorithm?

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Moved to General Discussions.

    It seems to me that if two algorithms with equivalent input arrive at different conclusions about the same deterministic property, then one or both algorithms must be incorrect (or the input is invalid).
    Last edited by laserlight; 04-24-2011 at 11:43 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User gaurav9991's Avatar
    Join Date
    Oct 2010
    Location
    Pune, Maharashtra, India
    Posts
    69
    thanks. I got it.

  4. #4
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    The algorithms can give you different (equal cost) trees. (In fact, two different implementations of the same algorithm could give you different results.) This can happen because there may be more than one minimal cost tree (a minimal spanning tree is not necessarily unique).

    Consider this graph.

    A -> B
    B -> C
    A -> C

    I can get the tree A -> B, A -> C or the tree A->B, B->C. If all edges have weight 1 then there are two minimal trees.

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Perspective
    The algorithms can give you different (equal cost) trees. (In fact, two different implementations of the same algorithm could give you different results.) This can happen because there may be more than one minimal cost tree (a minimal spanning tree is not necessarily unique).
    Good elaboration, but I note that the main part that answers the question is "(equal cost) trees", i.e., the value of the property (minimum cost of spanning of a weighted graph) is the same either way.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with Minimum Spanning Tree
    By Johnathank in forum C++ Programming
    Replies: 1
    Last Post: 09-27-2010, 03:25 AM
  2. Minimum Spanning Tree Shortest path
    By iamnew in forum C Programming
    Replies: 2
    Last Post: 06-18-2010, 12:37 AM
  3. Minimum Spanning Tree
    By iamnew in forum C++ Programming
    Replies: 1
    Last Post: 06-13-2010, 07:45 AM
  4. Minimum Spanning Tree
    By iamnew in forum C Programming
    Replies: 3
    Last Post: 06-06-2010, 04:54 PM
  5. Updated a Minimum Spanning Tree in O(V) time?
    By scp89 in forum C Programming
    Replies: 3
    Last Post: 05-07-2009, 02:02 PM