Commit | Line | Data |
---|---|---|
81e70d48 PH |
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. |