Minimum spanning trees

This is a discussion on Minimum spanning trees within the C Programming forums, part of the General Programming Boards category; I have to use the MST algorithm(Prim or Kruskal) in a program I'm developing. I would be very grateful if ...

  1. #1
    Registered User
    Join Date
    Feb 2002
    Posts
    3

    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
    Posts
    9,796
    Code:
    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
    Code:
    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
    -Prelude
    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, 03: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, 09:47 PM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  5. AVL Trees
    By kwigibo in forum C Programming
    Replies: 2
    Last Post: 04-17-2002, 06:46 PM

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