Thread: Prim's Kruskal Algorithm

  1. 06-16-2010 #1
    iamnew
    iamnew is offline
    Registered User
    Join Date
    Apr 2010
    Posts
    50

    Prim's Kruskal Algorithm

    What property of the graph will result in prim's and kruskal's algorithm giving different minimum spanning tree's?

    Please help.
  2. 06-16-2010 #2
    rklockow
    rklockow is offline
    Registered User
    Join Date
    Jun 2010
    Posts
    7
    I believe that if the graph allows for negative weights, then the two algorithms will produce different results.
  3. 06-16-2010 #3
    iamnew
    iamnew is offline
    Registered User
    Join Date
    Apr 2010
    Posts
    50
    are you sure that the algorithm runs for graph's containing negative edge's?
  4. 06-17-2010 #4
    Elysia
    Elysia is offline
    C++まいる！Cをこわせ！
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Prim's algorithm cannot handle negative edges. Kruskal, OTOH, doesn't care.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
  5. 06-19-2010 #5
    iamnew
    iamnew is offline
    Registered User
    Join Date
    Apr 2010
    Posts
    50
    can Prim’s yieeld different MST’s dependiing on which verteex was set as the startting point?
  6. 06-20-2010 #6
    Elysia
    Elysia is offline
    C++まいる！Cをこわせ！
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Do you have a theory? Have you thought about the question?
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
  7. 06-20-2010 #7
    iamnew
    iamnew is offline
    Registered User
    Join Date
    Apr 2010
    Posts
    50
    Quote Originally Posted by Elysia View Post
    Do you have a theory? Have you thought about the question?
    I don't get your point?

    I think it will not give different MST's when the starting vertex is changed

    Please help.
  8. 06-20-2010 #8
    Elysia
    Elysia is offline
    C++まいる！Cをこわせ！
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    I am asking if you have put any thought to the question. For example, have you tried to think what happens if you changed the starting point? Have you tried doing an experiment by writing down on a paper or some such?
    Why do you think it won't change?
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
  9. 06-20-2010 #9
    iamnew
    iamnew is offline
    Registered User
    Join Date
    Apr 2010
    Posts
    50
    i think the edges in the graph can change but the total edge cost cannot change. Any don't agree?
« Previous Thread | Next Thread »
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Appropriate container for prim's algorithm
    By Elysia in forum C++ Programming
    Replies: 6
    Last Post: 05-10-2010, 01:20 PM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. prims algorithm
    By condorx in forum C Programming
    Replies: 0
    Last Post: 11-09-2003, 06:20 AM