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.
Algorithm
The 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
|
Studies 
