Thread: Minimum Spanning Tree

  1. #1
    Registered User
    Join Date
    Apr 2010
    Posts
    50

    Minimum Spanning Tree

    Which algorithm is best suited to find the minimum spanning tree

    Kruskal algorithm or prim's algorithm?

    Which has the lowest time complexity?

    Please help.

  2. #2
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    It really depends on your input. I would say Prim's is better if you have a graph with a lot more edges than vertices. However, this depends on the data structure you are using in your implementation. You should read more online about the different options. A Fibonacci heap is usually what is required for an optimum Prim implementation.

    In any other cases I would go ahead and use Kruskal.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  3. #3
    Registered User
    Join Date
    Jun 2010
    Posts
    3
    I prefer Kruskal algorithm. It's realization with disjoint set union is much easiar to write, and it almost as quickly as Prim's algorithm with Fibonnaci heap.

  4. #4
    Registered User
    Join Date
    Mar 2009
    Posts
    399
    Use Kruskal's algorithm when you're only dealing with a low number of edges. Otherwise use Prim's algorithm.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 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
  2. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  3. 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
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM