Если по какому-то ребру мы пытаемся пройти во второй раз (т.е. есть цикл), то ... не надо туда идти
. Другими словами, каждое ребро может участвовать в пути лишь 1 раз.Я так понимаю, это NP-полная задача - здесь поможет только перебор.
Мне все это видится опять же через рекурсию. Т.к. мы пишем рекурсию, то вообразим себя уже где-то посередине процесса построения одного из путей, не задумываясь (пока не задумываясь) о начале и конце...
Итак, граф задан матрицей смежности. Мы находимся в вершине Аi, позади у нас есть какой-то путь (Aa - Ab - ... - Ah - Ai -).
Мы находимся в вершине Аi, позади у нас есть какой-то путь (Aa - Ab - ... - Ah - Ai -).
Смотрим на строку вершины Ai, ищем в ней "1".
Нашли "1" на позиции [i,j]:
помечаем ребро [i,j] как использованное (например, присваиваем этому элементу "-1")
добавляем в наш (текущий) путь Аj: Aa - Ab - ... - Ah - Ai - Aj
переходим к вершине Aj, смотрим на ее строку, ищем в ней "1", ...
Не нашли "1" нигде среди [i ][]: // т.е. пришли в конец текущего пути
сравниваем длину текущего пути с максимальной
удаляем из пути вершину Ai: Aa - Ab - ... - Ah
помечаем ребро [h,i] как неиспользованное ( [h][ i] = 1 )
смотрим на строку вершины Ah, ищем в [h][>i] "1" (начинаем с [h][i+1], т.к. в Ai мы уже пробовали ходить), ...
Теперь самое нелюбимое: условия выхода и начала :( .
Максимальный путь, естественно, равен нулю.
Мы хотим начать с нашей конкретно заданной вершины А0. Мы насильно записываем в начало пути А0. Ищем в А0 "1", ... .
Рано или поздно мы придем к тому, что не найдем в А0 "1" и захотим удалить А0 из пути, поднявшись на уровень вверх. По сути это будет попытка "удалить из пути вершину Аi при ( (i=0) и (длина текущего пути = 0) ) " и это будет значить, что мы уже рассмотрели все возможные пути, начинающиеся в А0, и переменная максимального пути уже содержит то, что нужно (короче пора делать return
).Причем условие про равенство длины текущего пути нулю обязательно и критически важно: если его опустить, то после пути типа (А0 - Аa - Ab - ... - Am - A0) мы не найдем пути (А0 - Аa-Ab- ... - Am - Ay), y>0. Мы просто не рассмотрим их, забудем, выбросим на помойку истории...
Правильно? Я упустила что-нибудь?
Посоветуйте, пожалуйста.
