CODEWITHSUNDEEP
c++algorithmgraphcycle
Cristian Sandu
Cristian Sandu

Reputation: 83

The longest cycle in an undirected graph

How i can get the longest cycle in a undirected Graph (without BackTracking, it takes too long).

Example:

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

Solve: 3 + 3 + 1 => Out: 1 - 2 - 3 - 1.

Upvotes: 1

Views: 2439

Answers (1)

Juan Lopes
Juan Lopes

Reputation: 10565

If you can find the longest cycle, you can detect whether the graph has a Hamiltonian Cycle, which is an NP-complete problem, thus making your problem NP-hard.

That means no solution will be fundamentally better than backtracking unless P=NP.

Upvotes: 4

Related Questions