Графы топологическая сортировка

Содержание

1. Графы топологическая сортировка
2. Постановка задачи топологической сортировкиДан ориентированный граф. Требуется
3. Пример топологической сортировки132465Исходный DAGВозможные результаты топологической сортировки:1
4. АлгоритмПереберём все вершины графа.Если вершина белая, то
5. Топологическая сортировка. Шаг 0Вектор с результатом:(пусто)132465
6. Топологическая сортировка. Шаг 1Вектор с результатом:(пусто)132465
7. Топологическая сортировка. Шаг 2Вектор с результатом:(пусто)132465
8. Топологическая сортировка. Шаг 3Вектор с результатом:(пусто)132465
9. Топологическая сортировка. Шаг 4Вектор с результатом:5132465
10. Топологическая сортировка. Шаг 5Вектор с результатом:5 – 3 132465
11. Топологическая сортировка. Шаг 6Вектор с результатом:5 – 3 132465
12. Топологическая сортировка. Шаг 7Вектор с результатом:5 – 3 132465
13. Топологическая сортировка. Шаг 8Вектор с результатом:5 – 3 132465
14. Топологическая сортировка. Шаг 9Вектор с результатом:5 – 3 132465
15. Топологическая сортировка. Шаг 10Вектор с результатом:5 – 3 132465
16. Топологическая сортировка. Шаг 11Вектор с результатом:5 – 3 – 6 132465
17. Топологическая сортировка. Шаг 12Вектор с результатом:5 – 3 – 6 – 4 132465
18. Топологическая сортировка. Шаг 13Вектор с результатом:5 – 3 – 6 – 4 – 2 132465
19. Топологическая сортировка. Шаг 14Вектор с результатом:5 –
20. Топологическая сортировка. Шаг 15Вектор с результатом:1 –
21. Реализация
22. Скачать презентанцию

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

Главная
Разное
Графы топологическая сортировка

Слайды и текст этой презентации

Слайд 1Графы топологическая сортировка
Школа::Кода
Олимпиадное программирование

2020-2021 Таганрог

Слайд 2Постановка задачи топологической сортировки
Дан ориентированный граф. Требуется пронумеровать его вершины

таким образом, чтобы каждое ребро вело из вершины с меньшим

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

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

Слайд 3Пример топологической сортировки
1
3
2
4
6
5
Исходный DAG
Возможные результаты топологической сортировки:
1 – 2 –

4 – 6 – 3 – 5
1 – 3 –

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

Пример топологической сортировки132465Исходный DAGВозможные результаты топологической сортировки:1 – 2 – 4 – 6 – 3 – 51

Слайд 4Алгоритм
Переберём все вершины графа.
Если вершина белая, то запустим из неё

поиск в глубину.
Во время поиска при выходе из вершины будем

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

АлгоритмПереберём все вершины графа.Если вершина белая, то запустим из неё поиск в глубину.Во время поиска при выходе

Слайд 5Топологическая сортировка. Шаг 0
Вектор с результатом:
(пусто)
1
3
2
4
6
5

Слайд 6Топологическая сортировка. Шаг 1
Вектор с результатом:
(пусто)
1
3
2
4
6
5

Слайд 7Топологическая сортировка. Шаг 2
Вектор с результатом:
(пусто)
1
3
2
4
6
5

Слайд 8Топологическая сортировка. Шаг 3
Вектор с результатом:
(пусто)
1
3
2
4
6
5

Слайд 9Топологическая сортировка. Шаг 4
Вектор с результатом:
5
1
3
2
4
6
5

Слайд 10Топологическая сортировка. Шаг 5
Вектор с результатом:
5 – 3
1
3
2
4
6
5

Слайд 11Топологическая сортировка. Шаг 6
Вектор с результатом:
5 – 3
1
3
2
4
6
5

Слайд 12Топологическая сортировка. Шаг 7
Вектор с результатом:
5 – 3
1
3
2
4
6
5

Слайд 13Топологическая сортировка. Шаг 8
Вектор с результатом:
5 – 3
1
3
2
4
6
5

Слайд 14Топологическая сортировка. Шаг 9
Вектор с результатом:
5 – 3
1
3
2
4
6
5

Слайд 15Топологическая сортировка. Шаг 10
Вектор с результатом:
5 – 3
1
3
2
4
6
5

Слайд 16Топологическая сортировка. Шаг 11
Вектор с результатом:
5 – 3 – 6

1
3
2
4
6
5

Слайд 17Топологическая сортировка. Шаг 12
Вектор с результатом:
5 – 3 – 6

– 4
1
3
2
4
6
5

Слайд 18Топологическая сортировка. Шаг 13
Вектор с результатом:
5 – 3 – 6

– 4 – 2
1
3
2
4
6
5

Слайд 19Топологическая сортировка. Шаг 14
Вектор с результатом:
5 – 3 – 6

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

Слайд 20Топологическая сортировка. Шаг 15
Вектор с результатом:
1 – 2 – 4

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

Слайд 21Реализация

Скачать презентацию

Разделы презентаций

Графы топологическая сортировка

Содержание

Слайды и текст этой презентации

Слайд 1Графы топологическая сортировка
Школа::Кода
Олимпиадное программирование

2020-2021 Таганрог

Слайд 2Постановка задачи топологической сортировки
Дан ориентированный граф. Требуется пронумеровать его вершины

таким образом, чтобы каждое ребро вело из вершины с меньшим

Слайд 3Пример топологической сортировки
1
3
2
4
6
5
Исходный DAG
Возможные результаты топологической сортировки:
1 – 2 –

4 – 6 – 3 – 5
1 – 3 –

Слайд 4Алгоритм
Переберём все вершины графа.
Если вершина белая, то запустим из неё

поиск в глубину.
Во время поиска при выходе из вершины будем

Слайд 5Топологическая сортировка. Шаг 0
Вектор с результатом:
(пусто)
1
3
2
4
6
5

Слайд 6Топологическая сортировка. Шаг 1
Вектор с результатом:
(пусто)
1
3
2
4
6
5

Слайд 7Топологическая сортировка. Шаг 2
Вектор с результатом:
(пусто)
1
3
2
4
6
5

Слайд 8Топологическая сортировка. Шаг 3
Вектор с результатом:
(пусто)
1
3
2
4
6
5

Слайд 9Топологическая сортировка. Шаг 4
Вектор с результатом:
5
1
3
2
4
6
5

Слайд 10Топологическая сортировка. Шаг 5
Вектор с результатом:
5 – 3
1
3
2
4
6
5

Слайд 11Топологическая сортировка. Шаг 6
Вектор с результатом:
5 – 3
1
3
2
4
6
5

Слайд 12Топологическая сортировка. Шаг 7
Вектор с результатом:
5 – 3
1
3
2
4
6
5

Слайд 13Топологическая сортировка. Шаг 8
Вектор с результатом:
5 – 3
1
3
2
4
6
5

Слайд 14Топологическая сортировка. Шаг 9
Вектор с результатом:
5 – 3
1
3
2
4
6
5

Слайд 15Топологическая сортировка. Шаг 10
Вектор с результатом:
5 – 3
1
3
2
4
6
5

Слайд 16Топологическая сортировка. Шаг 11
Вектор с результатом:
5 – 3 – 6

1
3
2
4
6
5

Слайд 17Топологическая сортировка. Шаг 12
Вектор с результатом:
5 – 3 – 6

– 4
1
3
2
4
6
5

Слайд 18Топологическая сортировка. Шаг 13
Вектор с результатом:
5 – 3 – 6

– 4 – 2
1
3
2
4
6
5

Слайд 19Топологическая сортировка. Шаг 14
Вектор с результатом:
5 – 3 – 6

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

Слайд 20Топологическая сортировка. Шаг 15
Вектор с результатом:
1 – 2 – 4

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

Слайд 21Реализация

Обратная связь

Что такое TheSlide.ru?

Разделы презентаций

Графы топологическая сортировка

Содержание

Слайды и текст этой презентации

Слайд 1Графы топологическая сортировкаШкола::КодаОлимпиадное программирование2020-2021 Таганрог

Слайд 2Постановка задачи топологической сортировкиДан ориентированный граф. Требуется пронумеровать его вершины

таким образом, чтобы каждое ребро вело из вершины с меньшим

Слайд 3Пример топологической сортировки132465Исходный DAGВозможные результаты топологической сортировки:1 – 2 –

4 – 6 – 3 – 51 – 3 –

Слайд 4АлгоритмПереберём все вершины графа.Если вершина белая, то запустим из неё

поиск в глубину.Во время поиска при выходе из вершины будем

Слайд 5Топологическая сортировка. Шаг 0Вектор с результатом:(пусто)132465

Слайд 6Топологическая сортировка. Шаг 1Вектор с результатом:(пусто)132465

Слайд 7Топологическая сортировка. Шаг 2Вектор с результатом:(пусто)132465

Слайд 8Топологическая сортировка. Шаг 3Вектор с результатом:(пусто)132465

Слайд 9Топологическая сортировка. Шаг 4Вектор с результатом:5132465

Слайд 10Топологическая сортировка. Шаг 5Вектор с результатом:5 – 3 132465

Слайд 11Топологическая сортировка. Шаг 6Вектор с результатом:5 – 3 132465

Слайд 12Топологическая сортировка. Шаг 7Вектор с результатом:5 – 3 132465

Слайд 13Топологическая сортировка. Шаг 8Вектор с результатом:5 – 3 132465

Слайд 14Топологическая сортировка. Шаг 9Вектор с результатом:5 – 3 132465

Слайд 15Топологическая сортировка. Шаг 10Вектор с результатом:5 – 3 132465

Слайд 16Топологическая сортировка. Шаг 11Вектор с результатом:5 – 3 – 6

132465

Слайд 17Топологическая сортировка. Шаг 12Вектор с результатом:5 – 3 – 6

– 4 132465

Слайд 18Топологическая сортировка. Шаг 13Вектор с результатом:5 – 3 – 6

– 4 – 2 132465

Слайд 19Топологическая сортировка. Шаг 14Вектор с результатом:5 – 3 – 6

– 4 – 2 – 1 132465

Слайд 20Топологическая сортировка. Шаг 15Вектор с результатом:1 – 2 – 4

– 6 – 3 – 5 132465

Слайд 21Реализация

Похожие презентации

Обратная связь

Что такое TheSlide.ru?

Слайд 1Графы топологическая сортировка
Школа::Кода
Олимпиадное программирование

2020-2021 Таганрог

Слайд 2Постановка задачи топологической сортировки
Дан ориентированный граф. Требуется пронумеровать его вершины

Слайд 3Пример топологической сортировки
1
3
2
4
6
5
Исходный DAG
Возможные результаты топологической сортировки:
1 – 2 –

4 – 6 – 3 – 5
1 – 3 –

Слайд 4Алгоритм
Переберём все вершины графа.
Если вершина белая, то запустим из неё

поиск в глубину.
Во время поиска при выходе из вершины будем

Слайд 5Топологическая сортировка. Шаг 0
Вектор с результатом:
(пусто)
1
3
2
4
6
5

Слайд 6Топологическая сортировка. Шаг 1
Вектор с результатом:
(пусто)
1
3
2
4
6
5

Слайд 7Топологическая сортировка. Шаг 2
Вектор с результатом:
(пусто)
1
3
2
4
6
5

Слайд 8Топологическая сортировка. Шаг 3
Вектор с результатом:
(пусто)
1
3
2
4
6
5

Слайд 9Топологическая сортировка. Шаг 4
Вектор с результатом:
5
1
3
2
4
6
5

Слайд 10Топологическая сортировка. Шаг 5
Вектор с результатом:
5 – 3
1
3
2
4
6
5

Слайд 11Топологическая сортировка. Шаг 6
Вектор с результатом:
5 – 3
1
3
2
4
6
5

Слайд 12Топологическая сортировка. Шаг 7
Вектор с результатом:
5 – 3
1
3
2
4
6
5

Слайд 13Топологическая сортировка. Шаг 8
Вектор с результатом:
5 – 3
1
3
2
4
6
5

Слайд 14Топологическая сортировка. Шаг 9
Вектор с результатом:
5 – 3
1
3
2
4
6
5

Слайд 15Топологическая сортировка. Шаг 10
Вектор с результатом:
5 – 3
1
3
2
4
6
5

Слайд 16Топологическая сортировка. Шаг 11
Вектор с результатом:
5 – 3 – 6

1
3
2
4
6
5

Слайд 17Топологическая сортировка. Шаг 12
Вектор с результатом:
5 – 3 – 6

– 4
1
3
2
4
6
5

Слайд 18Топологическая сортировка. Шаг 13
Вектор с результатом:
5 – 3 – 6

– 4 – 2
1
3
2
4
6
5

Слайд 19Топологическая сортировка. Шаг 14
Вектор с результатом:
5 – 3 – 6

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

Слайд 20Топологическая сортировка. Шаг 15
Вектор с результатом:
1 – 2 – 4

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