Реализация приведена на Python 3, поскольку в требованиях к практике указан Python.
Алгоритм считывает граф, изменяя направление рёбер в нём. Таким образом теперь задача найти все вершины, достижимые из множеств S1 и S2. Эта задача тривиально решается с помощью BFS (breadth-first search). Давайте добавим в очередь BFS все вершины из S1 и зададим для них расстояние от S1 равное 0. Запустим BFS и для каждой следующей обрабатываемой вершины будем указывать расстояние до S1 равное расстоянию для предка + 1. Таким образом мы можем посчитать расстояние от S1 до каждой вершины. Аналогично можно посчитать расстояние от S2 до каждой вершины. Теперь можно сложить расстояния для каждой вершины (исключив вершины, до которых нельзя дойти из S1 или S2) и останется отсортировать вершины по сумме расстояний. Это можно сделать сортировкой подсчётом, поскольку сумма длин путей не превышает 2 * количество вершин.
Построение графа происходит за O(N + M). Оба BFS также происходят за O(N + M). Сортировка подсчётом происходит за O(N), поскольку сумма длин путей не превышает 2 * N. Таким образом асимптотика алгоритма O(N + M) - алгоритм оптимален (быстрее решить эту задачу невозможно, поскольку считывание данных занимает O(N + M)).
Хорошая асимптотика не означает, что алгоритм работает быстро. При реализации я приоритизировал простоту над скоростью исполнения, поэтому использовал networkx для операций над графом. networkx внутри экстенсивно использует словари, однако для наших задач они излишни и нам бы хватило массивов статического размера. Подобными изменениями можно сильно ускорить алгоритм, однако с этим заметно увеличится и объём кода (от networkx скорее всего придётся отказаться). Если это критически важная часть кода и она должна выполняться на очень больших графах быстро, можно переписать на C/C++ и использовать C extension interface.
Дан ориентированный граф цитирования (вершины соответствуют научным статьям, ребро из А в В означает, что статья А ссылается на статью В), а также два множества вершин S1 и S2, соответствующих двум научным понятиям (например, это могли бы быть “интерфейс мозг-компьютер” и “VR”). Найти все вершины, из которых по ребрам графа цитирования достижимы оба множества S1 и S2. Отсортировать такие вершины по возрастанию суммарной длины путей, ведущих к заданным множествам.
Уточнение: множество S считается достижимым из вершины X, если хотя бы одна статья, входящая в S, достижима из вершины X.
Содержимое файла input.txt:
- Первая строка содержит числа N и M - число вершин и рёбер графа, соответственно.
- Следующие M строк содержат пару чисел от 1 до N, разделенные пробелом - начальную и конечную вершины, соответственно.
- Далее идёт информация о каждом из двух множеств: в первой строке количество вершин, входящих в множество, во второй строке номера вершин (от 1 до N).
11 10
3 1
3 2
4 6
5 7
8 4
8 5
10 4
11 5
9 10
9 11
2
6 1
2
2 7
Ожидаемый вывод - номера искомых вершин в порядке возрастания суммарной длины путей до заданных множеств (всё, что после # - комментарий):
3 # соответствует путям 1<3>2, длина путей = 2
8 # соответствует путям 6<4<8>5>7, длина путей = 4
9 # соответствует путям 6<4<10<9>11>5>7, длина путей = 6
Придумайте алгоритм для решения поставленной задачи и реализуйте его на языке программирования по вашему выбору, при выполнении можно пользоваться любыми сторонними библиотеками. Оцените вычислительную сложность алгоритма и добавьте в начало файла с кодом или README краткое описание алгоритма и оценку его сложности. Также напишите, какие альтернативные способы реализации видите и в чем могут быть их преимущества и недостатки.