极客笔记C++ 寻找是否可以根据给定条件仅一次访问给定图中的每个节点
介绍
图论在理解广泛的现实世界问题中起着关键作用，包括路径优化、网络分析和任务规划。图论中一个有趣的问题是寻找哈密顿路径，即一条恰好访问每个节点一次的路径。这个问题在电路设计、DNA测序和协调安排等领域有应用。本文深入研究了不同方法来确定根据一定条件是否可以仅一次访问给定图中的每个节点。我们重点关注三种具体算法：回溯算法、深度优先搜索(DFS)和带有剪枝的回溯算法。具体来说，我们使用C++编程语言展示了这些方法，提供了代码片段、逐步算法和每种方法的输出结果。
方法一：深度优先搜索(DFS)
深度优先搜索算法通过深度优先的方式遍历图中的所有可能路径。它使用一个栈来跟踪当前路径，并使用一个访问过的集合来检查已访问过的顶点。
算法
- 步骤1 - 从图的第一个顶点开始，标记为已访问。
-
步骤2 - 将当前顶点推入栈中，并将其添加到路径中。
-
步骤3 - 当栈不为空时 –
- 从栈中弹出顶点。
-
如果所有顶点都已访问过，则打印路径并返回true。
-
对于每个未访问过的相邻顶点，将其标记为已访问，推入栈中，并将其添加到路径中。
-
步骤4 - 如果栈变为空，则返回false。
示例
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
bool isSafe(int v, int pos, const vector<int>& path, const vector<vector<int>>& graph) {
if (graph[path[pos - 1]][v] == 0)
return false;
for (int i = 0; i < pos; ++i)
if (path[i] == v)
return false;
return true;
}
bool dfsUtil(const vector<vector<int>>& graph, vector<int>& path, vector<bool>& visited, int pos) {
int n = graph.size();
if (pos == n) {
for (int v : path)
cout << v << " ";
cout << endl;
return true;
}
for (int v = 1; v < n; ++v) {
if (!visited[v] && isSafe(v, pos, path, graph)) {
visited[v] = true;
path[pos] = v;
if (dfsUtil(graph, path, visited, pos + 1))
return true;
visited[v] = false;
path[pos] = -1;
}
}
return false;
}
void findHamiltonianPath(const vector<vector<int>>& graph) {
int n = graph.size();
vector<int> path(n, -1);
vector<bool> visited(n, false);
visited[0] = true; // Mark the first vertex as visited
path[0] = 0;
if (!dfsUtil(graph, path, visited, 1))
cout << "No Hamiltonian path exists." << endl;
}
int main() {
vector<vector<int>> graph = {
{0, 1, 1, 1},
{1, 0, 1, 0},
{1, 1, 0, 1},
{1, 0, 1, 0}
};
cout << "Depth-First Search (DFS):" << endl;
findHamiltonianPath(graph);
return 0;
}
输出
Depth-First Search (DFS):
0 1 2 3
方法2：回溯算法
回溯算法可以是一种有效地在图表内探索所有可能路径以发现哈密尔顿路径的蛮力约束方法，它使用递归函数，在遇到死胡同时回溯。
算法
- 步骤1 - 从图的第一个顶点开始。
-
步骤2 - 如果所有顶点都已经访问过，则打印路径并返回真。
-
步骤3 - 对于每个未访问过的相邻顶点，将其标记为已访问并加入路径。
-
步骤4 - 在路径中递归调用函数的下一个顶点。
-
步骤5 - 如果递归调用返回真，则路径是完整的。返回真。
-
步骤6 - 如果递归调用返回假，则通过将当前顶点标记为未访问并从路径中移除它进行回溯。
-
步骤7 - 如果没有更多相邻顶点可以探索，则返回假。
例子
#include <iostream>
#include <vector>
using namespace std;
bool isSafe(int v, int pos, const vector<int>& path, const vector<vector<int>>& graph) {
if (graph[path[pos - 1]][v] == 0)
return false;
for (int i = 0; i < pos; ++i)
if (path[i] == v)
return false;
return true;
}
bool hamiltonianPathUtil(const vector<vector<int>>& graph, vector<int>& path, int pos) {
if (pos == graph.size()) {
for (int v : path)
cout << v << " ";
cout << endl;
return true;
}
for (int v = 1; v < graph.size(); ++v) {
if (isSafe(v, pos, path, graph)) {
path[pos] = v;
if (hamiltonianPathUtil(graph, path, pos + 1))
return true;
path[pos] = -1; // Backtrack
}
}
return false;
}
void findHamiltonianPath(const vector<vector<int>>& graph) {
vector<int> path(graph.size(), -1);
path[0] = 0; // Start with the first vertex
if (!hamiltonianPathUtil(graph, path, 1))
cout << "No Hamiltonian path exists." << endl;
}
int main() {
vector<vector<int>> graph = {
{0, 1, 1, 1},
{1, 0, 1, 0},
{1, 1, 0, 1},
{1, 0, 1, 0}
};
cout << "Backtracking Algorithm:" << endl;
findHamiltonianPath(graph);
return 0;
}
输出
Backtracking Algorithm:
0 1 2 3
结论
在结论部分，我们研究了两种不同的方法来确定是否可能一次性访问每个图中的每个节点。这个问题被称为哈密顿路径问题，需要找到一条路径，每个节点都恰好访问一次，且不返回任何节点。首先，我们讨论了回溯算法，这种方法可以系统地探索图中的所有可能路径。该算法使用递归和回溯来找到一个有效的哈密顿路径。虽然计算代价可能很高，但回溯算法提供了一个直接的解决方案。