Thread: Minimum spanning trees

  1. #1
    Registered User
    Join Date
    Feb 2002

    Minimum spanning trees

    I have to use the MST algorithm(Prim or Kruskal) in a program I'm developing. I would be very grateful if someone could show me how to implement this algorithm.

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Kruskal's algorithm:
        sort the edges of G in increasing order by length
        keep a subgraph S of G, initially empty
        for each edge e in sorted order
            if the endpoints of e are disconnected in S
            add e to S
        return S
    Prim's algorithm:
        let T be a single vertex x
        while (T has fewer than n vertices)
            find the smallest edge connecting T to G-T
            add it to T
    My best code is written with the delete key.

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. Trees
    By masterg in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2008, 01:42 PM
  3. Displaying Minimum and Maximum values from input
    By mgardnertech in forum C Programming
    Replies: 1
    Last Post: 06-29-2008, 08:47 PM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  5. AVL Trees
    By kwigibo in forum C Programming
    Replies: 2
    Last Post: 04-17-2002, 05:46 PM