| 1 | PROGRAM MINIMALSPANNINGTREE(INPUT,OUTPUT); |
| 2 | |
| 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 *); |
| 6 | |
| 7 | |
| 8 | TYPE INDEX=INTEGER (* 0..NMAX *); |
| 9 | LENGTH=REAL (* RESULTTYPE OF FUNCTION 'DIST' *); |
| 10 | |
| 11 | |
| 12 | VAR N,H,K,I,LCR,SUV: INDEX; |
| 13 | |
| 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; |
| 21 | |
| 22 | |
| 23 | FUNCTION DIST(P,Q: INDEX): LENGTH; |
| 24 | BEGIN DIST := SQRT( SQR(X[P]-X[Q]) + SQR(Y[P]-Y[Q]) ) END; |
| 25 | |
| 26 | |
| 27 | |
| 28 | BEGIN |
| 29 | READ(N); WRITELN("THE",N:5," GIVEN POINTS ARE:"); |
| 30 | FOR K := 1 TO N DO |
| 31 | BEGIN READ(X[K],Y[K]); |
| 32 | WRITELN(K:3," (",X[K]:10:2,",",Y[K]:10:2,")":3) |
| 33 | END; |
| 34 | WRITELN; |
| 35 | |
| 36 | FOR K := 1 TO N-1 DO |
| 37 | BEGIN FROM[K] := 0; INTO[K] := K; UVL[K] := INF END; |
| 38 | LCR := N; |
| 39 | FOR K := 1 TO N-1 DO |
| 40 | BEGIN SUV := 0; MIN := INF; |
| 41 | FOR H := K TO N-1 DO |
| 42 | BEGIN LEN := DIST(LCR,INTO[H]); |
| 43 | IF LEN<UVL[H] THEN BEGIN UVL[H] := LEN; |
| 44 | FROM[H] := LCR |
| 45 | END |
| 46 | ELSE LEN := UVL[H]; |
| 47 | IF LEN<MIN THEN BEGIN MIN := LEN; SUV := H END |
| 48 | 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; |
| 52 | LCR := INTO[K] |
| 53 | END; |
| 54 | |
| 55 | WRITELN("THE MINIMAL SPANNING TREE IS:"); |
| 56 | SUM := ZER; |
| 57 | FOR K := 1 TO N-1 DO |
| 58 | BEGIN SUM := SUM + UVL[K]; |
| 59 | WRITELN(FROM[K]:5,"-":5,INTO[K]:5,UVL[K]:12:2) |
| 60 | END; |
| 61 | WRITELN(" ":15,"------------"); |
| 62 | WRITELN("TOTAL LENGTH: ",SUM:12:2) |
| 63 | END. |