Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!amdahl!pyramid!prls!philabs!linus!gateway.mitre.org!carlson
From: carlson@gateway.mitre.org (Bruce Carlson)
Newsgroups: comp.lang.pascal
Subject: Re: minimum spanning trees
Keywords: help
Message-ID: <44600@linus.UUCP>
Date: 7 Feb 89 14:58:21 GMT
References: <8854@ihlpl.ATT.COM>
Sender: news@linus.UUCP
Reply-To: carlson@gateway.mitre.org (Bruce Carlson)
Organization: The Mitre Corporation
Lines: 56

In article <8854@ihlpl.ATT.COM> canoura@ihlpl.ATT.COM (jlcanoura) writes:
>please I need help! Does any body know how to find
>the minimun spanning tree of a undirected weighted graph.
>any help will be appreciated.
>                                  J. Canoura
>                                  ihl/ihlpl


You can use Prim's method or Kruskal's algorithm.  They are explained
in "Fundamentals of Computer Algorithms", by Horowitz and Sahni, and
in several other books.

The general structure of these algorithms are below.  I think my method is
closer to Kruskal's, but I don't remember for sure.

Construct an adjacency table:  probably an array with node1, node2, distance;
  a linked list with a record structure will also work

Connect the two nodes with the smallest distance between them
Put these two nodes in an array or linked list (list is more efficient
  since size will vary)
{You will eventually have several of these lists}

Repeat this section
Select the node pair with the next smallest distance
Check the two endpoints to see if they are already both part of
  the same existing list.  
If they are both in the same existing list, throw this edge out
because it will create a cycle.
If they are not both in the same list there are two cases
  1. if they are each part of a different list, then they connect the
  two lists, so you concatenate the lists
  2. if only one endpoint is in an existing list, then this edge simply
  extends the existing list 

If have not connected all the nodes and are not at the end of the
 adjacency list, go back to select the next pair.
until all nodes are connected

Example:

adjacency list
                                             1
a-b  1            draw them as -          A------B
a-c  5            to illlustrate          |\5  / |  
a-d  4                                   4| \ /6 |3
b-c  3                                    |  /   |
b-d  6                                    | /  \ |
c-d  2                                    D------C
                                             2
connect a-b  {a,b}
connect c-d  {a,b}, {c,d}
connect b-c  {a,b,c,d}
all points are connected, cost is 6

Bruce Carlson