0
Как я могу получить самый длинный цикл в неориентированном Графе (без BackTracking, он занимает слишком много времени).Самый длинный цикл в неориентированном графе
Пример:
0 3 0 1 0
3 0 0 1 0
0 0 0 0 0
1 1 0 0 0
0 0 0 0 0
Решить: 3 + 3 + 1 => Выход: 1 - 2 - 3 - 1.
Если вы можете найти самый длинный цикл на графике за полиномиальное время, вы также решаете проблему цикла гамильтониана в полиномиальное время, что, как известно, является довольно сложной проблемой. Насколько велик ваш вклад, т. Е. Сколько вершин, ребер на вашем графике? – ead
Является ли это матрицей смежности? Если да, то что там делает «3» - у вас есть цветные края? Кроме того, вершины 3 и 5 отключены? – gilleain