建设网站中心,苏州吴江区城市建设局网站,邢台优化网站排名,网上写作如何投稿赚钱DFS算法查找所有路径详解
算法介绍
深度优先搜索#xff08;Depth-First Search#xff0c;DFS#xff09;是一种图遍历算法#xff0c;它从起始节点开始#xff0c;沿着一条路径尽可能深入#xff0c;直到达到最深的节点#xff0c;然后回溯到前一节点#xff0c;继…DFS算法查找所有路径详解
算法介绍
深度优先搜索Depth-First SearchDFS是一种图遍历算法它从起始节点开始沿着一条路径尽可能深入直到达到最深的节点然后回溯到前一节点继续探索下一条路径。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_setint visited, std::vectorint 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::coutnode ;}std::cout路径总长度为currentLengthstd::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();
}
