Поиск в глубину в ориентированных графах Топологическая сортировка

21.04.2014

ПВГ в орграфе

Особенности поиска в глубину (ПВГ) в ориентированных графах

21.04.2014

ПВГ в орграфе

Пример ПВГ в орграфе

1

2

3

4

(1)

5

6

7

(2)

(3)

(4)

(5)

(6)

(7)

8

9

10

(8)

(9)

(10)

Стоп!

21.04.2014

ПВГ в орграфе

Пример ПВГ в орграфе

1

2

3

4

(1)

5

6

7

(2)

(3)

(4)

(5)

(6)

(7)

8

9

10

(8)

(9)

(10)

Стоп!

Древесное ребро – от отца к

21.04.2014

ПВГ в орграфе

1

2

3

4

(1)

5

6

7

(2)

(3)

(4)

(5)

(6)

(7)

8

9

10

(8)

(9)

(10)

1

2

3

4

5

6

7

(1)

(5)

(4)

(3)

(2)

(6)

(7)

8

9

10

(8)

(9)

(10)

21.04.2014

ПВГ в орграфе

1

2

3

4

5

6

7

(1)

(5)

(4)

(3)

(2)

(6)

(7)

8

9

10

(8)

(9)

(10)

Направленное вперед ребро(u,v): n(u)в момент рассмотрения n(v)≠0

Древесное ребро (u,v):

21.04.2014

ПВГ в орграфе

Топологическая сортировка

Ациклический (бесконтурный) орграф
Лемма 1. Орграф G является ациклическим

21.04.2014

ПВГ в орграфе

Пример 0

1 (1)

4(2)

3(3)

2(4)

5(5)

1

2

3

4

5

2

1

3

4

5

(пере)нумерация
(vi,vj) ⇒ i

(пере)группировка
Все стрелки слева направо

Исходная нумерация

Нумерация

21.04.2014

ПВГ в орграфе

Продолжение примера 0 (ПВГ)

1

5

2

4

3

1

2

3

4

5

1

2

3

4

5

ПВГ (поиск в глубину)
1- номер в

21.04.2014

ПВГ в орграфе

Продолжение примера 0 (ПВГ)

v [*] – имена вершин в

21.04.2014

ПВГ в орграфе

Продолжение примера 0 (ПВГ)

1) Получение sn [*] из fn

21.04.2014

ПВГ в орграфе

Перестановки

tn [sn [ i ]] = i , где

21.04.2014

ПВГ в орграфе

Выполнить ПВГ в орграфе G, заполнив массив fn[*].
Пронумеровать вершины

21.04.2014

ПВГ в орграфе

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

Пример 1

1

2

3

4

5

6

7

1

2

3

4

5

6

7

a

b

c

d

e

f

g

21.04.2014

ПВГ в орграфе

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

Пример 2 (другие списки смежности)

1

7

6

4

1

3

2

3

6

5

4

2

5

7

1

2

3

4

5

6

7

1

2

3

4

5

6

7

21.04.2014

ПВГ в орграфе

Продолжение на следующей лекции! (28 апреля)

21.04.2014

ПВГ в орграфе

Нахождение сильно связных компонент графа (ССК)

Алгоритм на основе поиска

21.04.2014

ПВГ в орграфе

Сильно связные компоненты (Strongly Connected Components)

Сильно связная компонента –

21.04.2014

ПВГ в орграфе

1

2

3

4

(1)

5

6

7

(2)

(3)

(4)

(5)

(6)

(7)

8

9

10

(8)

(9)

(10)

1

2

3

4

5

6

7

(1)

(5)

(4)

(3)

(2)

(6)

(7)

8

9

10

(8)

(9)

(10)

Каждой ССК графа соответствует дерево в ПВГ-лесу
(более точно далее)

ПОИСК
в

21.04.2014

ПВГ в орграфе

Соответствие «ССК – дерево»

Утверждение
Пусть Gi =(Vi, Ei) – ССК

При стягивании каждой сильно связной компоненты в одну вершину получается ациклический

21.04.2014

ПВГ в орграфе

Обращение орграфа (понадобится далее), ССК – те же (!)

21.04.2014

ПВГ в орграфе

Алгоритм Косарайю (S.R.Kosaraju) нахождения ССК орграфа (на основе двух ПВГ)

Выполнить ПВГ

21.04.2014

ПВГ в орграфе

1

2

3

4

(1)

5

6

7

(2)

(3)

(4)

(5)

(6)

(7)

8

9

10

(8)

(9)

(10)

1

2

3

4

5

6

7

(1)

(5)

(4)

(3)

(2)

(6)

(7)

8

9

10

(8)

(9)

(10)

abde

hij

cfg

копия

21.04.2014

ПВГ в орграфе

Обращенный граф

(4)

(3)

(2)

(6)

(7)

(10)

(1)

(5)

(8)

(9)

I

II

(10)

(7)

III

(4)

ПВГ в обращенном графе

21.04.2014

ПВГ в орграфе

Основные факты (утверждения), на которые опирается доказательство правильности алгоритма

21.04.2014

ПВГ в орграфе

Пример (пояснение к утверждениям)

5/3

6/2

7/1

8/6

9/5

10/4

4/8

3/9

2/14

12/13

13/12

1/15

G

ПВГ в G

GССК

Топ. сорт. графа

21.04.2014

ПВГ в орграфе

Пример (продолжение)

13-3

15-2

14-1

10-6

12-5

11-4

9-8

7-9

3-14

2-13

4-12

1-15

GR

ПВГ в GR

(GR)ССК

A→ C → B → E

21.04.2014

ПВГ в орграфе

Сложность алгоритмов нахождения ССК

Алгоритм Тарьяна (Tarjan R.E.)
Алгоритм Косарайю (S.R.Kosaraju)
O(n