sw/src/pascal/MSTREE.PS

   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.