Определить, есть ли простой путь в графе, проходящий через все его вершины
Граф задан матрицей смежности. Необходимо определить, есть ли в нем хотя бы один простой путь, проходящий через все его вершины и если есть, вывести его на экран.
Каким алгоритмом лучше воспользоваться?
Ответы (1 шт):
Автор решения: Akina
→ Ссылка
Сначала считаете количество нечётных вершин. Если их больше двух - смело пишете, что пути нет.
Далее - обычный обход в глубину, ищется путь, длина которого на 1 меньше количества вершин, повторный проход не разрешён.
Если нечётных вершин две - ищем из одной в другую.
Если одна - из неё.
Если нет - из всех.
UPDATE
Пардон, ошибся. Написал для варианта прохода по всем рёбрам. Для прохода по всем узлам - просто поиск в глубину из всех узлов.