1 PROGRAM MINIMALSPANNINGTREE(INPUT,OUTPUT);
3 CONST NMAX=100; BMAX=99 (* BMAX=NMAX-1 *);
4 INF=99E99 (* LARGE VALUE OF TYPE LENGTH *);
5 ZER=0.0 (* ZERO VALUE OF TYPE LENGTH *);
8 TYPE INDEX=INTEGER (* 0..NMAX *);
9 LENGTH=REAL (* RESULTTYPE OF FUNCTION 'DIST' *);
12 VAR N,H,K,I,LCR,SUV: INDEX;
14 X,Y: ARRAY[1..NMAX] OF REAL;
15 (* POINT I DESCRIBED BY X[I],Y[I] *)
16 FROM,INTO: ARRAY[1..BMAX] OF INDEX;
17 (* BRANCH K DESCRIBED BY FROM[K],INTO[K] *)
18 UVL: ARRAY[1..BMAX] OF LENGTH;
19 (* UVL[K] CONTAINS LENGTH OF BRANCH K *)
20 MIN,LEN,SUM,L: LENGTH;
23 FUNCTION DIST(P,Q: INDEX): LENGTH;
24 BEGIN DIST := SQRT( SQR(X[P]-X[Q]) + SQR(Y[P]-Y[Q]) ) END;
29 READ(N); WRITELN("THE",N:5," GIVEN POINTS ARE:");
31 BEGIN READ(X[K],Y[K]);
32 WRITELN(K:3," (",X[K]:10:2,",",Y[K]:10:2,")":3)
37 BEGIN FROM[K] := 0; INTO[K] := K; UVL[K] := INF END;
40 BEGIN SUV := 0; MIN := INF;
42 BEGIN LEN := DIST(LCR,INTO[H]);
43 IF LEN<UVL[H] THEN BEGIN UVL[H] := LEN;
47 IF LEN<MIN THEN BEGIN MIN := LEN; SUV := H END
49 I := FROM[K]; FROM[K] := FROM[SUV]; FROM[SUV] := I;
50 I := INTO[K]; INTO[K] := INTO[SUV]; INTO[SUV] := I;
51 L := UVL[K]; UVL[K] := UVL[SUV]; UVL[SUV] := L;
55 WRITELN("THE MINIMAL SPANNING TREE IS:");
58 BEGIN SUM := SUM + UVL[K];
59 WRITELN(FROM[K]:5,"-":5,INTO[K]:5,UVL[K]:12:2)
61 WRITELN(" ":15,"------------");
62 WRITELN("TOTAL LENGTH: ",SUM:12:2)