Алгоритм поиска путей в графе

Привет, сегодня поговорим про алгоритм поиска путей в графе, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое алгоритм поиска путей в графе , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

Задание

Найти все возможные пути между двумя вершинами в графе не пеpесекающиеся по:
а) pебpам
б) веpшинам.

Ввод

Входящими данными является матрица смежности, составленная по такому правилу: C[i,j]=1, если в графе есть ребро (Ai,Aj) и C[i,j]=0 иначе.

Решение     [вверх]

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

Для поиска маршрута, не пересекающимся по вершинам, необходимо запоминать пройденные вершины и не совершать повторный проход по ним. Поиск текущего пути считается завершенным при достижении финишной вершины или невозможности добавления еще одного ребра в маршрут. Об этом говорит сайт https://intellect.icu . В любом случае после завершение построения текущего маршрута, мы возвращаемся на 1 шаг назад и пытаемся построить другой маршрут.

Для поиска маршрута, не пересекающимся по ребрам, необходимо создать массив-индикатор использования каждого ребра. Если ребро не было использовано, то метка для него истинна, иначе - ложная. Во время поиска маршрута прежде чем перейти к вершине мы проверяем, было ли использовано текущее ребро. Если не было, то мы добавляем его в маршрут и рекурсивно вызываем поиск для следующей вершины. При достижении "тупика" нахождении финишной вершины мы делаем шаг назад, считая последнее ребро в маршруте непройденным.

Формальное описание

Way()
1. Создать матрицу смежности для графа.
2. Прочитать номера стартовой и финишной вершины графа.
3. Инициализировать метки о использовании.
4. Добавить стартовую вершину в путь.
5. Найти все маршруты, не пересекающиеся по ребрам (пп.5.1-5.5):
   5.1. Если поиск вызван не со стартовой вершины, то считать последнее 
        ребро маршрута пройденным.
   5.2. Найти вершину, инцидентную данной.
   5.3. Если ребро, которое ведет к инцидентной вершине не было 
        использовано, то добавить вершину в путь, то считать ей 
        текущей и перейти к 5.1.
   5.4. Если финишная вершина достигнута, то вывести путь.
   5.5. Считать последнее ребро маршрута непройденным.
6. Найти все маршруты, не пересекающиеся по вершинам (пп.6.1-6.5):
   6.1. Присвоить текущей вершине номер шага.
   6.2. Найти вершину, инцидентную данной.
   6.3. Если инцидентная вершина не была использована, то считать ее 
        текущей, запомнить предыдущую вершину и перейти к п.6.1.
   6.4. Если финишная вершина достигнута, то вывести путь.
   6.5. Считать последнюю вершину маршрута непройденной.

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