42. Алгоритм топологической сортировки. Алгоритм нахождения расстояния от источника до всех остальных вершин в графе в случае бесконтурного графа. Оценка вычислительной сложности

Алгоритм топологической сортировки

Алгоритм генерирует последовательность согласованных меток для вершин бесконтурного орграфа. В самом начале работы алгоритма антецеденты каждой вершины записываются в множество A(v)

Пути в бесконтурном графе

Второй случай, для которого известен алгоритм нахождения расстояний от фиксированной вершины за время O(n²) — случай, когда граф является бесконтурным (веса дуг могут быть произвольными). Сначала докажем следующую лемму.

Лемма. В произвольном бесконтурном графе вершины можно перенумеровать так, что каждая дуга будет иметь вид v_i, v_j, где i < j.

Пример такой нумерации приведен на рисунке.

7 (3) 8

(1) (5)

t = 9

s = 1 (2) 4 (5) 5

(6) (4)

(1) (7) 6

(2) (10) (5)

2 3

Алгоритм нумерации вершин бесконтурного графа

Данные: Ориентированный бесконтурный граф V, E, определяемый списками инцидентности ЗАПИСЬ [v], v  V.

Результаты: Для каждой вершины v  V номер NR[v], такой что для произвольной дуги u, v  E выполняется неравенство NR[u] < NR[v].

1 begin

2 for v  V do ЧЗАХ [v] := 0;

{ ЧЗАХ [v] = число дуг, заходящих в v }

3 for u  V do

4 for v  ЗАПИСЬ [u] do ЧЗАХ [v] := ЧЗАХ [v] + 1;

5 СТЕК := ;

6 for v  V do

7 if ЧЗАХ [v] = 0 then СТЕК  v;

8 num := 0;

9 while СТЕК   do

10 begin u  СТЕК;

11 num := num + 1; NR[u] := num;

12 for v  ЗАПИСЬ [u] do

13 begin ЧЗАХ [v] := ЧЗАХ [v] – 1;

14 if ЧЗАХ [v] = 0 then СТЕК  v;

15 end

16 end

17 end

Алгоритм основывается на следующем простом факте: в произвольном (непустом) бесконтурном графе существует вершина, в которую не заходит ни одна дуга. Чтобы убедиться в этом, выберем произвольную вершину w₁ графа, затем некоторую вершину w₂, такую что w₂  w₁, затем вершину w₃, такую что w₃  w₂, и т.д. Через конечное число шагов мы должны дойти до некоторой вершины w_i, в которую не заходит ни одна дуга, ибо в силу бесконтурности ни одна вершина не может повторяться в последовательности w₁, w₂, w₃ , ... .

В нашем алгоритме вершины, в которые не заходит ни одна дуга, накапливаются в стеке. В строке 10 выбирается верхний элемент стека u (это мог бы быть произвольный элемент стека), и этой вершине присваивается самый маленький из еще неиспользованных номеров. Таким образом, мы гарантируем то, что все дуги, выходящие из этой вершины, ведут к вершине с большими номерами. Затем вершина u вместе с выходящими из нее дугами удаляется из графа. Это приводит к уменьшению на единицу числа дуг, заходящих в каждую вершину v, такую что u v ; это число запоминается в ЧЗАХ [v]. Если для какой-нибудь из вершин v это число сводится к нулю, то v помещается в стек.

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

Легко заметить, что каждая дуга анализируется алгоритмом один раз в строке 4 и один раз в строке 12. Таким образом, сложность алгоритма есть O(m) (остается в силе предположение m = (n), в противном случае следовало бы написать O(m + n)).

Примечание:

При сравнении скорости роста двух функций f(n) и g(n) (c неотрицательными значениями) мы, как обычно, используем следующие обозначения:

f(n) = O(g(n))  существуют константы С, N > 0, такие что f(n)  С g(n) для всех n  N

f(n) = (g(n))  существуют константы С, N > 0, такие что f(n)  С g(n) для всех n  N.

То есть, в частности, f(n) = (g(n)) тогда и только тогда, когда g(n) = O(f(n)).

Согласно вышеизложенному алгоритму при описании алгоритма нахождения путей в бесконтурном графе мы можем предположить, что каждая дуга идет из вершины с меньшим номером в вершину с большим номером.

Алгоритм нахождения расстояний от источника до всех вершин в бесконтурном графе

Данные: Ориентированный граф V, E, где V = {v₁, ... , v_n}, и для произвольной дуги v_i, v_j E имеем i < j. Этот граф определен списками инцидентности ПРЕДШ[v], v  V.

Результаты: Расстояния от v₁ до всех вершин графа:

D[v_i] = d(v₁, v_i), i = 1, ..., n.

1 begin

2 D[v₁] := 0;

3 for j := 2 to n do D[v_j] := ;

4 for j := 2 to n do

5 for v_i  ПРЕДШ [v_j] do D[v_j] := min(D[v_j]), D[v_i] + A[v_i, v_j])

6 end

Нетрудно доказать индукцией по j, что после выполнения цикла 4 для некоторого значения j выполняется равенство D[v_i] = d(v₁, v_i), i = 1, ..., j. Достаточно воспользоваться тем фактом, что все промежуточные вершины кратчайшего пути из v₁ в v_i имеют номера меньше j.

Сложность алгоритма порядка O(m), так как каждая дуга v_i, v_j анализируется а строке 5 в точности один раз.

Описанные алгоритмы находят применения, в частности, в методах управления выполнением проекта, называемых PERT (Project Evaluation and Review Technique) или CPM  (Critical Path Method). Эти методы основываются на построении графа (сети PERT или сети CPM), дуги которого соответствуют некоторым элементарным задачам, составляющим проект, а их веса указывают на время, необходимое для решения отдельных задач.

Кроме этого, мы предполагаем, что для произвольных дуг этого графа u, v и v, t задача, изображаемая дугой u, v, должна быть закончена перед началом решения задачи, изображаемой дугой v, t.

Легко заметить, что такой граф должен быть бесконтурным. Нашей задачей является нахождение самого длинного пути из вершины s, соответствующей началу проекта, до вершины t, соответствующей его окончанию. Такой путь называется критическим путем. Его длина определяет время, необходимое для реализации всего проекта. Очевидно, что задача сводится к задаче о кратчайшем пути путем изменения знака каждого веса a(u, v), где u  v, на обратный.