canoura@ihlpl.ATT.COM (jlcanoura) (02/07/89)
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
carlson@gateway.mitre.org (Bruce Carlson) (02/07/89)
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
zifrony@TAURUS.BITNET (02/13/89)
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