Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!TAURUS.BITNET!zifrony
From: zifrony@TAURUS.BITNET
Newsgroups: comp.lang.pascal
Subject: Re: minimum spanning trees
Keywords: help
Message-ID: <969@taurus.BITNET>
Date: 12 Feb 89 19:05:55 GMT
References: <8854@ihlpl.ATT.COM>
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: zifrony%sl2.UUCP@CUNYVM.CUNY.EDU (Zifrony Doron)
Organization: Tel-Aviv Univesity Math and CS school, Israel
Lines: 18


As far as I can recall without looking in a graph-algorithms book, the
algorithm used to solve this problem is a greedy algorithm.  I think the
algorithm was devised by Kruskal.  You start with an empty set of edges,
and a set of vertices containing one of the vertices in the graph.
In each step of the algorithm, each of the vertices in the vertices set
searches for the "cheapest" edge connected to him, which is not connected to
a member of the vertices set. This edge is added to the edges set, and the
vertex in the other side of the edge is added to the vertices set.
The algorithm continues until V is equal to the built set of vertices.

There was another algorithm to perform this task, but I can't recall it
right now, so try to contend yourself with this one.

Doron Zifrony           zifrony@taurus.bitnet  or  zifrony@Math.Tau.Ac.IL
Msc.  Student
Tel Aviv University
Israel