Prim's and Kruskal's minimum cost spanning tree

This is a discussion on Prim's and Kruskal's minimum cost spanning tree within the General Discussions forums, part of the Community Boards category; is it possible that the minimum cost of spanning of a weighted graph is different by Kruskal's algorithm and by ...

  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
    21,652
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    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
    21,652
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21