AVollane
@AVollane
Начинающий C# разработчик

Как найти количество путей в невзвешенном графе с символами в узлах?

Здравствуйте! Никак не могу понять алгоритмы поиска путей в графах. Прошу у вас помощи.
Граф - это схема дорог, где узлы - это города. Нужно найти самый длинный путь из А в М и общее количество путей.
6092b59264d5d381013530.png
Я понимаю, что здесь нужно использовать поиск в глубину, но я прочитал, что он просто находит самый длинный путь. А мне нужно, чтобы он ещё и подсчитывал количество возможных путей от А до М. Заранее спасибо! Буду благодарен любым объяснениям.
  • Вопрос задан
  • 118 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Точно также, как ищите наидлиннейший путь. Будет у вас DFS, который возвращает количество путей из заданной вершины до конечной, с заданными уже посещенными вершинами. В нем перебираете все исходящие ребра, запускаетесь рекурсивно (если конец ребра не посещен уже) и суммируете все результаты. Если пришли в конечную вершину - то возвращаете 1 (1 путь длины 0 - уже пришли). В начале функции помечайте вершину посещенной, чтобы в нее опять не входить. В конце функции помечайте вершину не посещенной, чтобы можно было другие пути через эту вершину считать. Разница с самым длинным путем в том, что вы тут суммируете результаты всех рекурсивных вызовов DFS, а не берете максимум. Ну и еще +1 не надо, как к длине, прибавлять.

Если граф ациклический, то можно использовать мемоизацию: результаты вычисления DFS для каждой начальной вершины сохраняйте (в глобальный массив, например) и никогда не считайте заново. При каждом вызове проверяйте, а не подсчитано ли значение уже и возвращайте его.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы