【DFS|BFS】最短路径问题

吃不饱的得可可

987人浏览 · 2025-07-11 14:20:35

吃不饱的得可可 · 2025-07-11 14:20:35 发布

迷宫探索者

走迷宫

BFS(广度优先搜索)与DFS(深度优先搜索)算法的适用场景及优缺点

迷宫探索者

BFS实现

vector<pair<int, int>> FindShortestPathBFS(vector<vector<int>> vv)
{
    int m = vv.size();
    int n = vv[0].size();
    const int dirs[4][2] = { {0,-1},{0,1},{1,0},{-1,0} };
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    unordered_map < pair<int, int>, pair<int, int>> parents;
    parents[make_pair(0, 0)] = { -1,-1 };
    vector<pair<int, int>> shortestPath;
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    visited[0][0] = true;

    while (!q.empty())
    {
        int x = (q.front()).first;
        int y = (q.front()).second;
        q.pop();
        if (x == m - 1 && y == n - 1)
        {
            for (auto p = make_pair(x, y);p != make_pair(-1, -1);p = parents[p])
            {
                shortestPath.emplace_back(p.first, p.second);
            }
            std::reverse(parents.begin(), parents.end()); //反转一下因为是回溯获取
            return shortestPath;
        }

        for (const auto& e : dirs) //二维数组也可以使用糖果for
        {
            int nx = x + e[0];
            int ny = y + e[1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && vv[nx][ny] == 0)
            {
                visited[nx][ny] = true;
                q.push(make_pair(nx, ny));
                parents[make_pair(nx, ny)] = make_pair(x, y);
            }
        }
    }
    return vector<pair<int,int>>();
}

DFS实现

DFS算法要对所有可能的路径进行比较然后获得到最短的路径，相较于BFS效率较低。

const int dirs[4][2] = { {-1,0},{-1,0},{1,0},{0,1} };
vector<pair<int, int>> currentPath;
void dfs(const vector<vector<int>>& vv, vector<vector<bool>>& visited, vector<pair<int, int>>& shortestPath,const pair<int,int> p)
{
    if (p.first == vv.size() - 1 && p.second == vv[0].size() - 1)
    {
        if (shortestPath.size() > currentPath.size() || shortestPath.empty())
        {
            shortestPath = currentPath;  //不能使用std::move来进行移动拷贝,currentPath中的节点要进行回溯
        }
        return;
    }
    for (const auto& e : dirs)
    {
        int nx = p.first + e[0];
        int ny = p.second + e[1];
        if (nx >= 0 && nx < vv.size() && ny >= 0 && ny < vv[0].size() && !visited[nx][ny] && vv[nx][ny] == 0)
        {
            currentPath.emplace_back(nx, ny);
            visited[nx][ny] = true;
            dfs(vv, visited, shortestPath, make_pair(nx, ny));
            visited[nx][ny] = false;
            currentPath.pop_back();
        }
    }
}
vector<pair<int, int>> ShortestPathDFS(vector<vector<int>> vv)
{
    int m = vv.size();
    int n = vv[0].size();
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    vector<pair<int, int>> shortestPath;
    currentPath.emplace_back(0, 0);
    dfs(vv, visited, shortestPath,make_pair(0,0));
    return shortestPath;
}

走迷宫

DFS实现需要尝试所有可能的路径，比较得到最短路径长度。

class solution2
{
public:
    vector<vector<int>> dirs = {{0,-1},{0,1},{-1,0},{1,0}};
    vector<vector<bool>> visited;
    int m = 0,n = 0;
    int dfs(const vector<vector<char>>& vv,int x,int y,int x2, int y2) 
    {
    	visited[x][y] = true;
        int tmp_length = INT_MAX;
        if(x == x2 && y == y2){
        	return 1;
		}
        for(const auto& e : dirs)
        {
        	int nx = x + e[0];
			int ny = y + e[1];
        	if(nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && vv[nx][ny] == '.')
        	{
        		tmp_length = std::min(tmp_length,dfs(vv,nx,ny,x2,y2));
			}
		}
		visited[x][y] = false;
		 return tmp_length == INT_MAX ? tmp_length : tmp_length + 1; 
    }
    
    int shortestLengthDFS(vector<vector<char>>& vv,int x1,int y1,int x2,int y2)
    {
        m = vv.size();
        n = vv[0].size();
        visited.resize(m, vector<bool>(n, false));
        visited[x1][y1] = true;
        int length = dfs(vv, x1, y1, x2, y2);
        if (vv[x2][y2] == '#' || length == INT_MAX) {
            return -1;
        }
        return length - 1;
    }

};

int main() 
{
	vector<vector<char>> vv = 
	{{'.','.','#'},
	 {'.','#','.'},
	 {'#','.','.'}
	};
	cout << solution2().shortestLengthDFS(vv,1,0,2,2) << endl;
	return 0;
}

BFS(广度优先搜索)与DFS(深度优先搜索)算法的适用场景及优缺点

BFS

寻找最短路径：在无权图或边权相等的图中，BFS 可以用来寻找从一个节点到其他节点的最短路径。例如，在走迷宫问题中（如上述代码所解决的问题），如果每一步的代价相同，BFS 可以找到从起点到终点的最少步数。这是因为 BFS 是一层一层地向外扩展搜索，先访问到的目标节点一定是距离起点最近的。
拓扑排序（在某些特定条件下）：对于一些具有特殊性质的图，如无环有向图（DAG），BFS 可以用于拓扑排序的一种实现方式。通过记录每个节点的入度，在图中找到所有入度为 0 的节点开始遍历，逐步减少其他节点的入度，最终可以得到一个拓扑序列。

优点

能保证找到最短路径：在无权图或边权相等的图中，BFS 能够确保找到的路径是距离最短的。
层次分明：搜索过程是按照层次进行的，易于理解和实现，并且可以方便地记录每个节点的深度信息。

缺点

空间复杂度较高：由于 BFS 需要存储每一层的节点，因此在搜索深度较大时，可能会占用大量的内存空间。例如，在搜索一棵非常深的树时，队列可能会迅速膨胀，导致内存不足。
对于大规模图可能效率较低：如果图的规模非常大，且目标节点距离起点较远，BFS 可能需要遍历大量的节点才能找到目标节点，从而导致时间复杂度较高。

DFS

寻找连通分量：DFS 可以用于在一个图中找出所有的连通分量。从一个未访问的节点开始，使用 DFS 遍历所有与之相连的节点，直到所有可达节点都被访问过，这样就可以找到一个连通分量。重复这个过程，直到图中的所有节点都被访问过。
拓扑排序（另一种实现方式）：DFS 可以用于有向无环图（DAG）的拓扑排序。在 DFS 的过程中，当一个节点的所有邻接节点都被访问完后，将该节点加入拓扑序列中。这样可以得到一个逆序的拓扑序列，再将其反转即可得到正确的拓扑序列。
路径查找（不要求最短路径）：在一些不需要找到最短路径的场景下，DFS 可以快速地找到从起点到终点的任意一条路径。例如，在八皇后问题中，DFS 可以用来尝试所有可能的皇后放置方案，直到找到一个满足条件的解。
解决迷宫问题（不要求最短路径）：如果只需要找到从起点到终点的一条路径，而不关心路径的长度，DFS 是一个不错的选择。它可以在迷宫中不断探索，直到找到出口。

优点