网站建设介绍的ppt,网站建设套模,桂林象鼻山图片,潍坊网站外包深度优先算法#xff08;Depth First Search#xff0c;DFS#xff09;是一种常见的图形算法#xff0c;它是一种用于遍历或搜索树或图的算法。在深度优先搜索中#xff0c;我们首先探索一个子树的深度#xff0c;然后再回溯到父节点#xff0c;接着探索另一个子树的深度…深度优先算法Depth First SearchDFS是一种常见的图形算法它是一种用于遍历或搜索树或图的算法。在深度优先搜索中我们首先探索一个子树的深度然后再回溯到父节点接着探索另一个子树的深度直至搜索结束。
深度优先算法的基本思想是沿着树的深度遍历树的节点。深度优先算法的工作原理类似于树的前序遍历即首先访问根节点然后依次访问该节点的子节点。
深度优先算法可以用递归实现也可以使用栈来实现。下面我们详细介绍这两种实现方式。
递归实现深度优先算法
下面是使用递归实现深度优先算法的示例代码
void dfs(int node, vector visited, vector graph) {// 标记节点node已被访问visited[node] true;// 访问节点nodecout node ;// 遍历node的所有邻居节点for (int i 0; i graph[node].size(); i) {int neighbor graph[node][i];// 如果邻居节点未被访问则递归访问它if (!visited[neighbor]) {dfs(neighbor, visited, graph);}}
}
在这个示例中我们首先定义一个函数dfs它接收三个参数分别是当前节点node、表示节点是否被访问的visited向量以及描绘图的邻接矩阵graph。在函数内部我们首先将当前节点标记为已访问并输出该节点的编号。然后我们遍历该节点的所有邻居节点如果邻居节点未被访问则递归地访问它。递归的终止条件是遍历完所有节点。
栈实现深度优先算法
下面是使用栈实现深度优先算法的示例代码
void dfs(int node, vector visited, vector graph) {stack stk;// 将起始节点入栈stk.push(node);while (!stk.empty()) {// 取出栈顶元素int cur stk.top();stk.pop();// 如果当前节点未被访问则访问它if (!visited[cur]) {visited[cur] true;cout cur ;// 将当前节点的邻居节点入栈for (int i graph[cur].size() - 1; i 0; i--) {int neighbor graph[cur][i];if (!visited[neighbor]) {stk.push(neighbor);}}}}
}
在这个示例中我们首先定义一个函数dfs它接收三个参数分别是当前节点node、表示节点是否被访问的visited向量以及描绘图的邻接矩阵graph。在函数内部我们创建一个栈并将初始节点node入栈。在栈未空之前我们重复执行以下步骤
取出栈顶元素如果当前节点未被访问则将其标记为已访问并输出该节点的编号遍历该节点的所有邻居节点如果邻居节点未被访问则将其入栈
在程序的最后我们完成了整个深度优先遍历。
深度优先算法的时间复杂度为$O(VE)$其中$V$是图的节点数量$E$是图的边数量。因为在遍历每个节点和边的时候每个节点和边都会被访问一次。另外深度优先算法的空间复杂度为$O(V)$其中$V$是图的节点数量因为需要存储每个节点的访问状态。
