最短时间学会基于C++实现DFS深度优先搜索攻略
什么是DFS深度优先搜索
DFS即深度优先搜索,是一种基于搜索算法的遍历和检索树或图数据结构的算法。DFS算法采用深度优先策略,从根结点出发访问所有可达结点,直到叶子节点。在访问某个结点时,先访问该结点的第一个未访问的相邻节点,然后递归的访问其非相邻节点。其搜索的核心思想是根据某个搜索方向向前搜索到底,直至无法继续下去时就回到上一个结点重新选择另一片区域搜索,直至所有结点都被访问。
实现DFS深度优先搜索
方式一:递归实现DFS深度优先搜索
递归实现DFS深度优先搜索比较简单,只需要实现以下三个步骤:
- 判断当前节点是否已经被访问过,如果访问过,返回。
- 将当前节点标记为已访问。
- 对当前节点的所有未被访问过的临界节点进行访问,递归重复以上步骤。
void dfs(int cur, vector<vector<int>>& graph, vector<bool>& visited) {
visited[cur] = true;
for (int i = 0; i < graph[cur].size(); i++) {
int neighbor = graph[cur][i];
if (!visited[neighbor]) {
dfs(neighbor, graph, visited);
}
}
}
方式二:栈实现DFS深度优先搜索
使用栈来实现DFS深度优先搜索的方法,具备更好的可读性和可维护性。由于需要遍历到所有未访问的节点,因此不能直接用栈进行遍历,需要将根节点压入栈内,然后使用while循环进行遍历,直到栈为空。
void dfs(int start, vector<vector<int>>& graph, vector<bool>& visited) {
stack<int> s;
s.push(start);
while (!s.empty()) {
int cur = s.top();
s.pop();
if (visited[cur]) continue;
visited[cur] = true;
for (int i = graph[cur].size() - 1; i >= 0; i--) {
int neighbor = graph[cur][i];
if (!visited[neighbor]) {
s.push(neighbor);
}
}
}
}
示例1:图的遍历
例如,我们要遍历一个图,对该图进行DFS深度优先搜索,可以使用以下代码:
int main() {
vector<vector<int>> graph(5);
graph[0].push_back(1);
graph[1].push_back(2);
graph[2].push_back(3);
graph[3].push_back(4);
graph[4].push_back(1);
vector<bool> visited(5, false);
dfs(0, graph, visited);
return 0;
}
以上代码中,我们以图中的0号节点为起始节点,进行深度优先遍历。
示例2:迷宫的搜索
以下代码提供一个方格迷宫搜索的示例,使用DFS深度优先搜索解决,其中,我们使用了递归。
int maze[5][5] = {
{ 0, 0, 0, 0, 1 },
{ 0, 1, 0, 1, 0 },
{ 0, 0, 0, 1, 0 },
{ 1, 1, 0, 0, 0 },
{ 0, 0, 1, 0, 0 }
};
bool visited[5][5];
int dstX = 4, dstY = 4;
bool dfs(int curX, int curY) {
if (curX < 0 || curY < 0 || curX >= 5 || curY >= 5 || visited[curX][curY] || maze[curX][curY] == 1) {
return false;
}
if (curX == dstX && curY == dstY) {
return true;
}
visited[curX][curY] = true;
if (dfs(curX-1, curY) || dfs(curX+1, curY) || dfs(curX, curY-1) || dfs(curX, curY+1)) {
return true;
}
visited[curX][curY] = false;
return false;
}
总结
以上是两种实现DFS深度优先搜索的方法及其示例解决方案。简单的递归实现可以快速实现,但是在处理效率相对较低的情况下会出现栈空间不足的问题,此时栈毕竟是有限大小的,如果栈深度过大会导致程序崩溃。栈实现的方法则可以避免这个问题。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:最短时间学会基于C++实现DFS深度优先搜索 - Python技术站