Longest Simple Cycle Problem
The Longest Simple Cycle problem seeks to find the longest simple cycle in a graph. A simple cycle is a cycle that doesn’t repeat any vertices except the first and last. This problem can appear in various applications like network design and route optimization.
In more accessible terms, imagine a network of cities connected by roads. What is the longest route you can take that visits each city only once and returns to the starting city?
Example Code in Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 // Example code assumes that the graph is represented as an adjacency matrix
public class LongestSimpleCycle {
static int longestCycle(int[][] graph, boolean[] visited, int currNode, int startNode, int length) {
if (currNode == startNode && length > 0) return length;
visited[currNode] = true;
int maxLength = 1;
for (int i = 0; i < graph.length; i++) {
if (graph[currNode][i] > 0 && !visited[i]) {
int cycleLength = longestCycle(graph, visited, i, startNode, length + 1);
maxLength = Math.max(maxLength, cycleLength);
}
}
visited[currNode] = false;
return maxLength;
}
public static void main(String[] args) {
int[][] graph = { // your adjacency matrix here };
boolean[] visited = new boolean[graph.length];
System.out.println(longestCycle(graph, visited, 0, 0, 0));
}
}

Example Code in C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 #include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int longestCycle(vector<vector<int>> &graph, vector<bool> &visited, int currNode, int startNode, int length) {
if (currNode == startNode && length > 0) return length;
visited[currNode] = true;
int maxLength = 1;
for (int i = 0; i < graph.size(); ++i) {
if (graph[currNode][i] > 0 && !visited[i]) {
int cycleLength = longestCycle(graph, visited, i, startNode, length + 1);
maxLength = max(maxLength, cycleLength);
}
}
visited[currNode] = false;
return maxLength;
}
int main() {
vector<vector<int>> graph; // Your adjacency matrix here
vector<bool> visited(graph.size(), false);
cout << longestCycle(graph, visited, 0, 0, 0) << endl;
}

Example Code in Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 def longest_cycle(graph, visited, curr_node, start_node, length):
if curr_node == start_node and length > 0:
return length
visited[curr_node] = True
max_length = 1
for i in range(len(graph)):
if graph[curr_node][i] > 0 and not visited[i]:
cycle_length = longest_cycle(graph, visited, i, start_node, length + 1)
max_length = max(max_length, cycle_length)
visited[curr_node] = False
return max_length
graph = [] # Your adjacency matrix here
visited = [False for _ in range(len(graph))]
print(longest_cycle(graph, visited, 0, 0, 0))

In all implementations, the algorithm explores all possible cycles starting from each node. It uses a DepthFirst Search (DFS) approach to find the longest simple cycle. Note that this is an exponential time solution.