Minimum Spanning Tree

Suppose there are six cities. Connections between cities are known. How can we find the shortest root from one city to the ending city? Every path must be passed only once.

The Algorithm

Pascal Source Code

{
   This program finds minimum spanning tree for given connection points
   and distances between them.

mst[]   :  Stores input connection information, type is  record.
             .d1 : node 1
             .d2 : node 2
             .uz : distance between 1. and 2.
tree[]  :  Stores minimum spanning tree.
check[] :  control array.

}

uses crt;
type
  rec = record
    d1:byte;
    d2:byte;
    uz:word;
   end;
var
  mst,tree:array[1..100] of  rec; i,j,k,l,m,n,t1,t2,s:integer;
  check:array[1..50] of byte; ch:char;
BEGIN
  clrscr;
  write('Number of nodes: ');readln(n);
  write('Number of connections:');readln(m);
  writeln('Input node numbers and distances in sorted order...');
  k:=3;
  for i:=1 to m do
    begin
     gotoxy(1,k+i);write('Node 1:');read(mst[i].d1);
     gotoxy(15,k+i);write('Node 2:');read(mst[i].d2);
     gotoxy(28,k+i);write('distance:');read(mst[i].uz);
    end;
  writeln;
  i:=1; s:=1;l:=0;
  while i<=n do
   begin
    t1:=mst[i].d1;
    t2:=mst[i].d2;
    if check[t1]+check[t2]=0 then
begin
          check[t1]:=s;
          check[t2]:=s;
          inc(s); inc(l);
          tree[l]:=mst[i];
         end
    else if check[t1]*check[t2]=0 then
        begin
         k:=t1+t2;
         check[t1]:=k;
         check[t2]:=k;
         inc(s); inc(l);
         tree[l]:=mst[i];
        end
    else if check[t1]<>check[t2] then
       if check[t1]<check[t2] then
        begin
         for j:=1 to i-1 do
           if (mst[j].d1=t2)or(mst[j].d2=t2) then
             begin
              check[mst[j].d1]:=check[t1];
              check[mst[j].d2]:=check[t1];
              inc(l);
              tree[l]:=mst[i];
             end;
         inc(s);
        end
       else if check[t1]>check[t2] then
        begin
         for j:=1 to i-1 do
           if (mst[j].d1=t1)or(mst[j].d2=t1) then
             begin
              check[mst[j].d1]:=check[t2];
              check[mst[j].d2]:=check[t2];
              inc(l);
              tree[l]:=mst[i];
             end;
         inc(s);
        end;
    inc(i);
   end;
  writeln(‘Minimum Spinning Tree…’);
  write('Node 1');for i:=1 to l do write(tree[i].d1:3); writeln;
  write('Node 2');for i:=1 to l do write(tree[i].d2:3); writeln;
  write('Distance ');for i:=1 to l do write(tree[i].uz:3); writeln;
  repeat ch:=readkey until ch=#27; { Esc Exit }
END.

Sample Execution

Number of nodes: 6

Number of connections:9

Input node numbers and distances in sorted order...

Node 1:1 Node 2:6 Distance:1

Node 1:4 Node 2:5 Distance:2

Node 1:2 Node 2:3 Distance:2

Node 1:1 Node 2:5 Distance:3

Node 1:6 Node 2:5 Distance:3

Node 1:3 Node 2:4 Distance:4

Node 1:1 Node 2:2 Distance:4

Node 1:2 Node 2:5 Distance:5

Node 1:2 Node 2:4 Distance:6

Node 1 1 4 2 1 3

Node 2 6 5 3 5 4

Distance 1 2 2 3 4