DFS算法查找所有路径详解

DFS算法查找所有路径详解

算法介绍

深度优先搜索（Depth-First Search，DFS）是一种图遍历算法，它从起始节点开始，沿着一条路径尽可能深入，直到达到最深的节点，然后回溯到前一节点，继续探索下一条路径。DFS通常使用递归或栈（非递归）来实现。

以下是DFS算法的基本步骤：

• 选择起始节点： 从图中选择一个起始节点作为当前节点；
• 标记节点： 标记当前节点为已访问，以防止重复访问；
• 探索邻居节点： 对于当前节点的未访问邻居节点，选择一个邻居节点作为新的当前节点，然后重复步骤2和步骤3；
• 回溯： 如果当前节点没有未访问的邻居节点，回溯到上一节点，重复步骤3；
• 重复过程： 重复步骤3和步骤4，直到所有节点都被访问。

递归实现的伪代码

function DFS(node):if node is not visited:mark node as visitedfor each neighbor of node:DFS(neighbor)

非递归实现的伪代码

DFS的非递归实现通常使用栈来模拟递归调用的过程，具体步骤如下：

• 创建一个空栈，并将起始节点压入栈中；
• 进入循环，直到栈为空；
• 弹出栈顶节点作为当前节点；
• 如果当前节点未访问，标记为已访问；
• 遍历当前节点的邻居节点，将未访问的邻居节点压入栈中；
• 重复步骤3到步骤5，直到栈为空为止。

注意：在处理连通图时可能导致栈溢出，因此在实际应用中可能需要注意栈深度的问题。
伪代码如下：

function DFS_non_recursive(start):stack = empty stackpush start onto stackwhile stack is not empty:current = pop from stackif current is not visited:mark current as visitedfor 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();
}