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

Question

[Антон Барышев]

Здравствуйте! Никак не могу понять алгоритмы поиска путей в графах. Прошу у вас помощи.
Граф - это схема дорог, где узлы - это города. Нужно найти самый длинный путь из А в М и общее количество путей.

Я понимаю, что здесь нужно использовать поиск в глубину, но я прочитал, что он просто находит самый длинный путь. А мне нужно, чтобы он ещё и подсчитывал количество возможных путей от А до М. Заранее спасибо! Буду благодарен любым объяснениям.

Answer 1

[Wataru]

Точно также, как ищите наидлиннейший путь. Будет у вас DFS, который возвращает количество путей из заданной вершины до конечной, с заданными уже посещенными вершинами. В нем перебираете все исходящие ребра, запускаетесь рекурсивно (если конец ребра не посещен уже) и суммируете все результаты. Если пришли в конечную вершину - то возвращаете 1 (1 путь длины 0 - уже пришли). В начале функции помечайте вершину посещенной, чтобы в нее опять не входить. В конце функции помечайте вершину не посещенной, чтобы можно было другие пути через эту вершину считать. Разница с самым длинным путем в том, что вы тут суммируете результаты всех рекурсивных вызовов DFS, а не берете максимум. Ну и еще +1 не надо, как к длине, прибавлять.

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

Comments

[Антон Барышев]

Спасибо, попробую.