§ Иллюстрация

§ Код

1DECLARE SUB DrawCircles (VSel!, VSeek!)
2SCREEN 13
3
4CONST n = 6
5
6'    1 2 3 4 5 6
7DATA 0,9,0,2,4,0 : REM 1 -> 2,4,5
8DATA 0,0,4,0,0,1 : REM 2 -> 3,6
9DATA 0,0,0,7,0,0 : REM 3 -> 4
10DATA 0,0,0,0,1,3 : REM 4 -> 5,6
11DATA 0,0,0,0,0,1 : REM 5 -> 6
12DATA 0,0,0,0,0,0 : REM 6 -> 4
13
14' Graphs point
15'    Y   X
16DATA 4,  20 : REM 1
17DATA 9,  11 : REM 2
18DATA 9,  29 : REM 3
19DATA 16, 11 : REM 4
20DATA 16, 29 : REM 5
21DATA 21, 20 : REM 6
22
23DIM SHARED G(n, n) AS INTEGER
24DIM SHARED W(n) AS INTEGER
25DIM SHARED PG(n, 2) AS INTEGER
26DIM SHARED VIS(n) AS INTEGER
27DIM SHARED Best(n) AS INTEGER
28
29' Чтение матрицы весов
30FOR i = 1 TO n: FOR j = 1 TO n: READ G(i, j): NEXT: NEXT
31FOR i = 1 TO n: READ PG(i, 1): READ PG(i, 2): W(i) = -1: VIS(i) = 0: NEXT
32
33' Назначение нулевого веса
34W(1) = 0
35
36' Первая отрисовка
37DrawCircles 0, 0: SLEEP 0
38
39DO
40
41  ' Выбор следующей вершины
42  NextVertex = 0
43  FOR i = 1 TO n
44
45    IF VIS(i) = 0 AND W(i) >= 0 THEN
46      NextVertex = i
47      EXIT FOR
48    END IF
49
50  NEXT
51
52  IF NextVertex THEN
53
54    DrawCircles NextVertex, 2
55
56    ' Просмотр прилегающих вершин
57    FOR j = 1 TO n
58
59      ' Проверка не посещенной вершины только
60      IF G(NextVertex, j) AND VIS(j) = 0 THEN
61
62        DrawCircles NextVertex, j: SLEEP 0
63
64        ' Проверка ребра
65        CW = G(NextVertex, j)
66
67        ' Если вершина не взвешена или ее значение больше
68        IF W(j) = -1 OR W(j) > CW THEN
69
70          ' Увеличиваем значение ребра
71          W(j) = W(NextVertex) + CW
72
73          ' Выбор лучшей точки
74          Best(j) = NextVertex
75
76          ' Снова нарисовать выбранную точку
77          DrawCircles NextVertex, j: SLEEP 0
78
79        END IF
80
81      END IF
82
83    NEXT
84
85    ' Отметка, что вершина посещена
86    VIS(NextVertex) = 1
87
88  END IF
89
90LOOP WHILE NextVertex > 0
91
92SUB DrawCircles (VSel, VSeek)
93
94  CLS
95  COLOR 7
96
97  ' Нарисовать линии от кружков
98  FOR i = 1 TO n
99  FOR j = 1 TO n
100
101    IF G(i, j) THEN
102
103      x1 = PG(i, 2) * 8 - 5: y1 = PG(i, 1) * 8 - 5
104      x2 = PG(j, 2) * 8 - 5: y2 = PG(j, 1) * 8 - 5
105
106      xr = x1 * .2 + x2 * .8
107      yr = y1 * .2 + y2 * .8
108
109      xm = (x1 + x2) \ 2
110      ym = (y1 + y2) \ 2
111      LOCATE ym \ 8 + 1, xm \ 8
112      PRINT G(i, j);
113
114      LINE (x1, y1)-(x2, y2), 8
115      LINE (xr, yr)-(x2, y2), 14
116
117    END IF
118
119  NEXT
120  NEXT
121
122  ' Кружки и подписи к ним
123  FOR i = 1 TO n
124
125    x% = PG(i, 2)
126    y% = PG(i, 1)
127    LOCATE y%, x%
128
129    ' Рисуется кружок
130    xs% = x% * 8 - 5
131    ys% = y% * 8 - 5
132
133    cl = 15
134    IF VSel = i THEN cl = 12 ELSE cl = 15
135    IF VSeek = i THEN cl = 13
136    IF VIS(i) THEN cl = 6
137
138    CIRCLE (xs%, ys%), 9, cl
139    PAINT (xs%, ys%), 0, cl
140
141    IF VIS(i) THEN COLOR 6 ELSE COLOR 10
142    PRINT LTRIM$(STR$(i));
143
144    COLOR 9
145    IF i <= 3 THEN y% = y% - 2 ELSE y% = y% + 2
146    LOCATE y%, x% - 1: PRINT W(i)
147
148  NEXT
149
150  ' Таблица рекордов
151  COLOR 3
152  FOR i = 1 TO n
153    LOCATE i, 1: PRINT i; CHR$(27); Best(i);
154  NEXT
155
156END SUB