TUZ_3-13 Сортировка циклов в графе
3.13 Сортировка циклов в графе
Цикл в графе – это путь, который начинается и заканчивается в одной и той же вершине.
Рассмотрим массив G, заполненный положительными целыми числами. Каждое число в G является вершиной графа.
Цель этой задачи состоит в том, чтобы найти циклы в G и отсортировать их в некотором порядке.
Например, пусть G = [2, 4, 6, 5, 3, 1, 0] и нужно найти циклы такие, в которых большее число образует первую вершину;
вершины, позиции или индексы которых находятся после позиции с наибольшим числом, вставляются после позиции с наибольшим числом;
а уже за этими вершинами вставляются вершины, позиции или индексы которых находятся перед позицией с наибольшим числом.
Далее необходимо отсортировать все циклы в порядке возрастания.
Рассмотрим порядок решения задачи для нашего примера.
- Первая вершина в G содержит число 2, какое число находится в индексе 2?
Поскольку индексация в Python начинается с нуля, мы получаем число 6.
- Следующий шаг: какое число находится в индексе 6? Это число 0.
- Следующий шаг: какое число находится в индексе 0? Это число 2,
следовательно, мы нашли цикл 2 → 6 → 0 → 2. Вставляем в список первый цикл, C = [[2, 6, 0]].
- Первая вершина, которую мы не посещали, – это число 4. Она считается первой вершиной следующего цикла.
- Следующий шаг: какое число стоит в индексе 4? Это число 3.
- Следующий шаг: какое число находится в индексе 3? Это число 5.
- Следующий шаг: какое число находится в индексе 5? Это число 1.
- Следующий шаг: какое число находится в индексе 1? Это число 4.
Найден еще один цикл, 4 → 3 → 5 → 1 → 4. Добавляем его в список циклов C = [[2, 6, 0], [4, 3, 5, 1]].
- Теперь в G не осталось вершин, которые мы не посетили, поэтому выполняем процесс сортировки.
- Для [2, 6, 0] наибольшее число (вершина) равно 6, поэтому [2, 6, 0] → [6], 0 помещаем после 6, поэтому [6] → [6, 0], а 2 предшествовало 6, поэтому [6, 0] → [6, 0,2]. Получаем обновленные циклы: C = [[6, 0, 2], [4, 3, 5, 1]].
- Во втором цикле [4, 3, 5, 1] наибольшее число равно 5, поэтому [4, 3, 5, 1] → [5].
За числом 5 в цикле следует 1, поэтому 1 вставляется после 5, а перед 5 мы имеем 4 и 3,
поэтому добавляем 4 и 3 после 5 и 1.
- В результате получаем циклы C = [[6, 0, 2], [5, 1, 4, 3]].
- На следующем шаге циклы сортируются по возрастанию, и получается C = [[6, 0, 2], [5, 1, 4, 3]] → C = [[5, 1, 4, 3], [6, 0, 2]].
- На последнем этапе вложенные массивы форматируются и преобразуются в единый плоский массив: С = [5, 1, 4, 3, 6, 0, 2].
Ваша задача: написать функцию, которая принимает массив G и возвращает отсортированные циклы.
В табл. 3.13 показаны ожидаемые результаты для некоторых входных данных.
| Таблица 3.13. Некоторые ожидаемые результаты для задачи поиска и сортировки циклов в граф |
| G |
Ожидаемый результат |
| [1, 2, 4, 5, 3, 0] |
[5, 0, 1, 2, 4, 3] |
| [1, 2, 3, 4, 0] |
[4, 0, 1, 2, 3] |
| [4, 3, 7, 0, 1, 5, 2, 6] |
[4, 1, 3, 0, 5, 7, 6, 2] |
| [1, 3, 5, 0, 2, 4] |
[3, 0, 1, 5, 4, 2] |