Математическая логика и теория алгоритмов. Стенюшкина В.А. - 80 стр.

     Рассмотрим способ ускорения поиска в сети. Пусть решается задача
определения выходов (рисунок 4.3). Считаем, что S представлена в оператив-
ной памяти в виде массива дуг µ (таблица 4.1).

                       3                          4                      5
                                     4                       2
                3                1               2
                                                             5
            1          5             6
                                                                             1     3

                2                1               3               2

                      7                              8                   9
                                                 Рисунок 4.3

       Отсортируем файл y по ключу х. В этом случае среднее время нахожде-
ния всех дуг (х, у) даже при последовательном поиске сократится примерно
вдвое.
        Таблица 4.1

 Индекс х           Дуга у               d               Индекс      х           Дуга у   d
      1   7                  8               3                9          1            3       3
      2   3                  4               4               10          1            7       2
      3   5                  9               1               11          6            4       2
      4   9                  5               3               12          1            6       5
      5   4                  5               2               13          6            8       3
      6   8                  9               1               14          6            5       5
      7   3                  6               1               15          6            9       2
      8   7                  6               1

      Пусть имеется некоторый вспомогательный массив А, в позициях x кото-
рого записан адрес А(х) расположения в µ начальной дуги вида (x, y). В этом
случае проблема поиска всех дуг (x, y) сводится к выборам адреса А(х). Если,
например, требуется найти в µ все дуги вида (х0, у), то получив А(х0) = у0 мы
попадаем на подмассив выходов из х0. Этот способ решения задачи полагает,
что х∈Р – это натуральные числа. Для минимизации объема дополнительной
памяти, то есть величина t=maxx∈P(x), удобно иметь последовательную нумера-
цию вершин, начиная с 1.
      Теперь о второй задаче. Если отсортировать µ по у, то удастся построить
аналогичный простой механизм поиска входов в конкретную вершину. Однако,
чтобы не потерять возможность эффективно решать предыдущую задачу, по-
ступим следующим образом. Введем два массива В(х) и С(х). Массив В(х) уст-