DFS算法查找所有路径详解
算法介绍
深度优先搜索（Depth-First Search，DFS）是一种图遍历算法，它从起始节点开始，沿着一条路径尽可能深入，直到达到最深的节点，然后回溯到前一节点，继续探索下一条路径。DFS通常使用递归或栈（非递归）来实现。
以下是DFS算法的基本步骤：
- 选择起始节点： 从图中选择一个起始节点作为当前节点；
- 标记节点： 标记当前节点为已访问，以防止重复访问；
- 探索邻居节点： 对于当前节点的未访问邻居节点，选择一个邻居节点作为新的当前节点，然后重复步骤2和步骤3；
- 回溯： 如果当前节点没有未访问的邻居节点，回溯到上一节点，重复步骤3；
- 重复过程： 重复步骤3和步骤4，直到所有节点都被访问。
递归实现的伪代码
function DFS(node):
if node is not visited:
mark node as visited
for each neighbor of node:
DFS(neighbor)
非递归实现的伪代码
DFS的非递归实现通常使用栈来模拟递归调用的过程，具体步骤如下：
- 创建一个空栈，并将起始节点压入栈中；
- 进入循环，直到栈为空；
- 弹出栈顶节点作为当前节点；
- 如果当前节点未访问，标记为已访问；
- 遍历当前节点的邻居节点，将未访问的邻居节点压入栈中；
- 重复步骤3到步骤5，直到栈为空为止。
注意：在处理连通图时可能导致栈溢出，因此在实际应用中可能需要注意栈深度的问题。
伪代码如下：
function DFS_non_recursive(start):
stack = empty stack
push start onto stack
while stack is not empty:
current = pop from stack
if current is not visited:
mark current as visited
for each neighbor of current:
push neighbor onto stack
具体算法实现
由于可能存在非常多的路径，我们设置一个maxLength，表示限制经过的节点个数。
void Graph::DFS(int current, int end, std::unordered_set<int>& visited, std::vector<int>& path, int maxLength)
{
static int currentLength = 0;
static int i = 1;
visited.insert(current);
path.push_back(current);
if (path.size() <= maxLength)
{
if (current == end)
{
// 生成路径
for (int node : path)
{
std::cout<<node<<' ';
}
std::cout<<"路径总长度为："<<currentLength<<std::endl;
}
else
{
for (int neighbor = 0; neighbor < V; ++neighbor)
{
if (adjMatrix[current][neighbor] != INF && visited.find(neighbor) == visited.end())
{
int edgeWeight = adjMatrixLength[current][neighbor];
currentLength += edgeWeight;
DFS(neighbor, end, visited, path, maxLength);
currentLength -= edgeWeight; // 回溯时减去当前边的长度
}
}
}
}
visited.erase(current);
path.pop_back();
}
