构造哈密顿回路c++

构造哈密顿回路是指在一个无向图中找到一条经过每个顶点恰好一次且最后回到起点的路径。这是一个经典的计算机科学问题，尤其在图论和算法设计中有重要意义。在C++中，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）等算法来寻找哈密顿回路。

以下是使用深度优先搜索的一个简单示例：

#include <vector>
#include <stack>

// 图节点的结构体
struct Node {
    int value;
    std::vector<Node*> neighbors; // 存储相邻节点
};

bool isHamiltonianCycle(Node* graph, int n) {
    // 使用vis[]标记节点是否已经访问过
    std::vector<bool> vis(n, false);
    vis[0] = true; // 设置起始节点已访问

    std::stack<Node*> stack; // DFS栈
    stack.push(graph);

    while (!stack.empty()) {
        Node* node = stack.top();
        stack.pop();

        // 如果找到了回路并且最后一个节点是起始节点，则返回true
        if (node == graph && stack.empty()) {
            return true;
        }

        for (Node* neighbor : node->neighbors) {
            if (!vis[neighbor->value]) {
                vis[neighbor->value] = true;
                stack.push(neighbor);
            }
        }
    }

    return false; // 没有找到回路
}

int main() {
    // 初始化图的数据...
    Node* graph = ...;

    int numVertices = ...;
    if (isHamiltonianCycle(graph, numVertices)) {
        std::cout << "存在哈密顿回路" << std::endl;
    } else {
        std::cout << "不存在哈密顿回路" << std::endl;
    }

    return 0;
}