使用BFS查找所有哈密顿周期

Question

我知道这个主题有很多线程，但是我发现的话题没有帮助我。 我必须在使用BFS的无向图上找到所有哈密顿周期。我有搜索一个周期的代码（不是哈密顿式），现在我需要修改它，这是我的问题。我不确定如何以适当的方式进行递归思考。

我的想法是，为了找到全部使用BFS，我需要：

• 跟踪一个可能的周期（路径）。
• 保留访问节点数量的数量。如果我到达具有源为父源的“ N”节点，则需要检查是否已经访问了所有节点。

因此，为了拥有一个哈密顿周期，我必须只访问所有节点一次，然后在我到达访问访问的节点的节点时完成，并且“源”与“源”相邻。

这是我的图。

https://i.sstatic.net/sildn.png

，这是我的代码

#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;
}

吗？谢谢大家。

Answer 1

看起来您的代码当前正在寻找图表中的简单（非汉密尔顿）周期。如果我们添加到条件if（parent [u]！= v）{return true; }检查是否访问了所有顶点（访问 的所有元素必须为true），然后看来代码可以正常工作。

Answer 2

添加没有做您认为的事情。

1. adj旨在是图形的邻接矩阵。正如矩阵所暗示的那样这需要二维。

2 （自动V：adj [u]）没有任何意义。 adj [u]是一个int，因此“迭代”上面的“迭代”是没有意义的。

我的建议是：退后一步，在解决这样的先进问题之前立即获得基本面。基于正确实现的邻接矩阵创建实际的图形类。用简单的内容测试您的课程，例如使用BF列出所有可及的节点。一旦有效，您就可以开始面临更大的挑战。