Backtracking algorithm to find out if the graph has a simple cycle with n vertices

Question

I'm trying to create a backtracking algorithm which finds out if the given graph has a simple cycle with k amount of vertices. My current approach is this:

def simpleCycle(A, k, visited, currentNode):   # A = adjacency matrix, k = amount of vertices, visited = list of visited nodes


    visited.append(currentNode)

    if len(visited) == k and A[currentNode][visited[0]] == 1:
        return True

    for neighbor in range(len(A[currentNode])):
        if neighbor not in visited and A[currentNode][neighbor] == 1 and len(visited) < k:
            if simpleCycle(A, k, visited, neighbor):
                return True

    visited.pop()
    return False


A = [[0, 1, 0, 1, 0],
     [1, 0, 1, 0, 0],
     [0, 1, 0, 1, 1],
     [1, 0, 1, 0, 1],
     [0, 0, 1, 1, 0]]

print(simpleCycle(A, 3, [], 0))

I've put it in python visualizer and I found out what the problem was. For my example I used this graph with the corresponding Adjacency matrix:

This code finds all the simple paths which start on the given starting node which is 1 in my example. The problem is that I don't know how to change the very first starting node, since I give it as an argument to the function. Now it finds the correct solution for k = 4 and k = 5. But for k = 3 it has to start at a different node than 1. Which the current algorithm can not do.

Now the question is: How do I change my code that after checking every solution for starting node 1, it also changes the starting node.

Pseudocode solution given:

Thanks in advance!

Answer 1

How do I change my code that after checking every solution for starting node 1, it also changes the starting node.

That would not be an efficient solution. Instead you can keep the algorithm where you start at one particular node (assuming the graph is connected).

The trick is to mark each node that you visit with the distance you have travelled to it. Then when you encounter a node that you already visited on the way, you can look at the difference in distance. If that difference is k, you have a hit! We can use visited to both indicate the fact that a node was visited, and with which distance. If we start the distance counting from 1, then the value 0 can indicate the node has not yet been visited.

Code:

def simpleCycle(A, k):
    visited = [0] * len(A)
    
    def dfs(currentNode, depth):
        if visited[currentNode]:
            return visited[currentNode] == depth - k
        visited[currentNode] = depth
        for neighbor in range(len(A[currentNode])):
            if A[currentNode][neighbor]:  # edge
                if dfs(neighbor, depth + 1):
                    print("true", currentNode, "to", neighbor)
                    return True
        visited[currentNode] = 0
        return False

    return dfs(0, 1)

A = [[0, 1, 0, 1, 0],
     [1, 0, 1, 0, 0],
     [0, 1, 0, 1, 1],
     [1, 0, 1, 0, 1],
     [0, 0, 1, 1, 0]]

print(simpleCycle(A, 3))