0

У меня есть ориентированный граф введите сюда описание изображения

Мне нужно сделать вот такой перебор:
Берём вершину 2. Перебираем все пути от вершины 2 до вершины 3 (один путь: 2->3). Далее перебираем все вершины от 2 до 4 (два пути: 2->3->4, 2->4). Далее от 2 до 5 и до самой последней (здесь до 5)

В общем, для каждой вершины перебрать все пути до других вершин.
Два вопроса:

Как сделать этот перебор в графе представленном матрицей смежности, можно код на Python
Возможно ли это оптимизировать, потому что перебирать столько путей будет очень медленно

1 ответ 1

1

Используйте доработанный поиск в ширину (или в глубину)

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

Это можно осуществить, передавая новый экземпляр пометок (visited) в рекурсивный вызов, либо работать с одним экземпляром, но очищать пометку обрабатываемой вершины после рекурсивного вызова.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.