Случайный афоризм
Подлинно великие писатели - те, чья мысль проникает во все изгибы их стиля. Виктор Мари Гюго
 
новости
поиск по автору
поиск по тематике
поиск по ключевому слову
проба пера
энциклопедия авторов
словарь терминов
программы
начинающим авторам
ваша помощь
о проекте
Книжный магазин
Главная витрина
Книги компьютерные
Книги по психологии
Книги серии "Для чайников"
Книги по лингвистике
ЧАВо
Разные Статьи
Статьи по литературе

Форма пользователя
Логин:
Пароль:
регистрация
 детектив



 драмма



 животные



 история



 компьютерная документация



 медицина



 научно-популярная



 очередная история



 очерк



 повесть



 политика



 поэзия и лирика



 приключения



 психология



 религия



 студенту



 технические руководства



 фантастика



 философия и мистика



 художественная литература



 энциклопедии, словари



 эротика, любовные романы



в избранноеконтакты

Параметры текста
Шрифт:
Размер шрифта: Высота строки:
Цвет шрифта:
Цвет фона:

отдельно. (б) Выбрав цвет одной вершины и обходя ее связную ком-
поненту, мы определяем единственно возможный цвет остальных.

     Замечание.  В  этой задаче безразлично, производить поиск в
ширину или в глубину.

     9.2.4. Составить нерекурсивный алгоритм топологической сор-
тировки  ориентированного  графа без циклов. (См. задачу 7.4.2 в
главе о рекурсии.)

     Решение.  Предположим,  что  граф  имеет вершины с номерами
1..n, для каждой вершины i известно число  num[i]  выходящих  из
нее ребер и номера вершин dest[i][1],..., dest[i][num[i]], в ко-
торые эти ребра ведут. Будем условно считать, что ребра перечис-
лены "слева направо": левее то ребро, у которого  номер  меньше.
Нам надо напечатать все вершины в таком порядке, чтобы конец лю-
бого ребра был напечатан перед его началом. Мы предполагаем, что
в графе нет ориентированных циклов - иначе такое невозможно.
      Для начала добавим к графу вершину 0, из которой ребра ве-
дут в вершины 1,...,n. Если ее удастся напечатать с  соблюдением
правил, то тем самым все вершины будут напечатаны.

      Алгоритм  хранит путь, выходящий из нулевой вершины и иду-
щий по ребрам графа. Переменная l отводится для длины этого  пу-
ти.  Путь  образован  вершинами  vert[1],..., vert[l] и ребрами,
имеющими номера edge[1]...edge[l]. Номер edge[s] относится к ну-
мерации ребер, выходящих из вершины vert[s]. Тем самым для  всех
s должны выполняться неравенство
        edge[s] <= num[vert[s]]
и равенство
        vert[s+1] = dest [vert[s]] [edge[s]]
Впрочем,  для  последнего  ребра мы сделаем исключение, разрешив
ему указывать "в пустоту",  т.е.  разрешим
edge[l] равняться num[vert[l]]+1.

     В  процессе  работы  алгоритм будет печатать номера вершин,
при этом соблюдая требование "вершина  напечатана  только  после
тех вершин, в которые из нее ведут ребра". Наконец, будет выпол-
няться такое требование:

(И)     вершины  пути, кроме последней (т.е. vert[1]..vert[l])
        не напечатаны, но свернув с пути налево, мы немедленно
        упираемся в напечатанную вершину

Вот что получается:

        l:=1; vert[1]:=0; edge[1]:=1;
        while not( (l=1) and (edge[1]=n+1)) do begin
        | if edge[l]=num[vert[l]]+1 then begin
        | | {путь кончается в пустоте, поэтому все вершины,
        | |     следующие за vert[l], напечатаны - можно
        | |     печатать vert[l]}
        | | writeln (vert[l]);
        | | l:=l-1; edge[l]:=egde[l]+1;
        | end else begin
        | |  {edge[l] <= num[vert[l]], путь кончается в
        | |     вершине}
        | |  lastvert:= dest[vert[l]][edge[l]]; {последняя}
        | |  if lastvert напечатана then begin
        | |  | edge[l]:=edge[l]+1;

1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : 10 : 11 : 12 : 13 : 14 : 15 : 16 : 17 : 18 : 19 : 20 : 21 : 22 : 23 : 24 : 25 : 26 : 27 : 28 : 29 : 30 : 31 : 32 : 33 : 34 : 35 : 36 : 37 : 38 : 39 : 40 : 41 : 42 : 43 : 44 : 45 : 46 : 47 : 48 : 49 : 50 : 51 : 52 : 53 : 54 : 55 : 56 : 57 : 58 : 59 : 60 : 61 : 62 : 63 : 64 : 65 : 66 : 67 : 68 : 69 : 70 : 71 : 72 : 73 : 74 : 75 : 76 : 77 : 78 : 79 : 80 : 81 : 82 : 83 : 84 : 85 : 86 : 87 : 88 : 89 : 90 : 91 : 92 : 93 : 94 : 95 : 96 : 97 : 98 : 99 : 100 : 101 : 102 : 103 : 104 : 105 : 106 : 107 : 108 : 109 : 110 : 111 : 112 : 113 : 114 : 115 : 116 : 117 : 118 : 119 : 120 : 121 : 122 : 123 : 124 : 125 : 126 : 127 : 128 : 129 : 130 : 131 : 132 : 133 : 134 : 135 : 136 : 137 : 138 : 139 : 140 : 141 : 142 : 143 : 144 : 145 : 146 : 147 : 148 : 149 : 150 : 151 : 152 : 153 : 154 : 155 : 156 : 157 : 158 : 159 : 160 : 161 : 162 : 163 : 164 : 165 : 166 : 167 : 168 : 169 : 170 : 171 : 172 : 173 : 174 : 175 : 176 : 177 : 178 : 179 : 180 : 181 : 182 : 183 : 184 : 185 : 186 : 187 : 188 : 189 : 190 : 191 : 192 : 193 : 194 : 195 : 196 : 197 : 198 : 199 : 200 : 201 : 202 : 203 : 204 : 205 : 206 : 207 : 208 : 209 : 210 : 211 : 212 : 213 : 214 : 215 : 216 : 217 : 218 : 219 : 220 : 221 : 222 : 223 : 224 : 225 : 226 : 227 : 228 : 229 : 230 : 231 : 232 : 233 : 234 : 235 : 236 : 237 : 238 : 239 : 240 : 241 : 242 : 243 : 244 : 245 : 246 : 247 : 248 : 249 : 250 : 251 : 252 : 253 : 254 : 255 : 256 : 257 : 258 : 259 : 260 : 261 : 262 : 263 : 264 : 265 : 266 : 267 : 268 : 269 : 270 : 271 : 272 : 273 : 274 : 275 : 276 : 277 : 278 : 279 : 280 : 281 : 282 : 283 : 284 : 285 : 286 : 287 : 288 : 289 : 290 : 291 : 292 : 293 : 294 : 295 : 296 : 297 : 298 : 299 : 300 : 301 : 302 : 303 : 304 : 305 : 306 : 307 : 308 : 309 : 310 : 311 : 312 : 313 : 314 : 315 : 316 : 317 : 318 : 319 : 320 : 321 : 322 : 323 : 324 : 325 : 326 : 327 : 328 : 329 : 330 : 331 : 332 : 333 : 334 : 335 : 336 : 337 : 338 : 339 : 340 : 341 : 342 : 343 : 344 : 345 : 346 : 347 : 348 : 349 : 350 : 351 : 352 : 353 : 354 : 355 : 356 : 357 : 358 : 359 : 360 : 361 : 362 : 363 : 364 : 365 : 366 : 367 : 368 : 369 : 370 : 371 : 372 : 373 : 374 : 375 : 376 : 377 : 378 : 379 : 380 : 381 : 382 : 383 : 384 : 385 : 386 : 387 : 388 : 389 : 390 : 391 : 392 : 393 : 394 : 395 : 396 : 397 : 398 : 399 : 400 : 401 : 402 : 403 : 404 : 405 : 406 : 407 : 408 : 409 : 410 : 411 : 412 : 413 : 414 : 415 : 416 : 417 : 418 : 419 : 420 : 421 : 422 : 423 : 424 : 425 :
главная наверх

(c) 2008 Большая Одесская Библиотека.