I know there's so many threads about this topic, but none of the ones I have found had helped me. I have to find all the Hamiltonian cycles on a undirected graph using BFS. I have the code that search for a cycle (not hamiltonian), now I need to modify it and here's my problem. I'm not sure how to do this in a proper manner without thinking recursiverly.

My thoughts are that in order to find all Hamiltonian cycles using BFS I need:

• Keep a track of one possible cycle (path).
• Keep a count of the numbers of visited nodes. If I arrive to a "n" node that has the source as parent, I will need to check if all nodes are already visited.

So, in order to have a Hamiltonian Cycle, I must visit all nodes only once and finish when I arrive to a node that is inside of visited ones and that has "source" as adjacent.

Here's my graph.

https://i.stack.imgur.com/siLDn.png

And here's my code

#include <bits/stdc  .h>
using namespace std;

void addEdge(vector<int> adj[], int u, int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
} 
// return true if there's a cycle on the graph
bool thereIsCycle(vector<int> adj[], int s, int V)
   {
    // Mark all the vertices as not visited
    vector<bool> visited(V, false);

    // Set parent vertex for every vertex as -1.
    vector<int> parent(V, -1);

    // Create a queue for BFS
    queue<int> q;

    // Mark the current node as
    // visited and enqueue it
    visited[s] = true;
    q.push(s);
 
    while (!q.empty()) {
 
        // Dequeue a vertex from queue and print it
        int u = q.front();
        q.pop();
 
        // Get all adjacent vertices of the dequeued
        // vertex u. If a adjacent has not been visited,
        // then mark it visited and enqueue it. We also
        // mark parent so that parent is not considered
        // for cycle.
        for (auto v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
                parent[v] = u;
            }
            else if (parent[u] != v){
                return true;
            }
                
        }
    }
    return false;
}    
int main()
{
    int V = 4;
    vector<int> adj[V];
    addEdge(adj, 0, 1);
    addEdge(adj, 1, 2);
    addEdge(adj, 2, 0);
    addEdge(adj, 2, 3);
    // check if there is a cycle from node 0
    if (thereIsCycle(adj, 0, V)){
        cout << "Yes";
    }else{
        cout << "No";
    }
 
    return 0;
}

Any suggests? Thank you all.

CodePudding user response：

It looks like your code is currently looking for simple (non-Hamiltonian) cycles in the graph. If we add to the condition if (parent[u] != v){ return true; } checking that all vertices have been visited (all elements of the visited must be true), then it looks like the code will work correctly.

CodePudding user response：

addEdge is not doing what you think it is.

1. Adj is intended to be the adjacency matrix of the graph. As implied by matrix this needs to be two dimensional.

2 for (auto v : adj[u]) makes no sense. adj[u] is an int, so it is meaningless to 'iterate' over it.

My suggestion: Take a step back and get the fundamentals right before tackling such an advanced problem. Create an actual graph class based on a correctly implemented adjacency matrix. Test you class with something simple, say listing all reachable nodes using BFS. Once that is working you can begin to move onto bigger challenges.