LC周报-深度优先搜索(20221121-20221127)

本周做题记录

LC-116、LC-117、LC-124、LC-133、LC-199，LC-130, LC-200, LC-207, LC-210,涉及知识深度优先搜索。本文选取典型，简要介绍深度优先搜索在图、树以及其他相关问题上的应用。

本周总结 1-深度优先搜索

LC-130 被围绕的区域、LC-200 岛屿数量

这两道题都是对一个方格矩阵进行深度优先遍历。

200题的题解如下：

class Solution {
public:
    void dfs(vector<vector<char>>& grid, int x, int y)
    {
        int n = grid.size();
        int m = grid[0].size();
        if(x<0 || x>=n || y<0 || y>=m || grid[x][y] == '0')
        return;

        grid[x][y] = '0';
        dfs(grid, x+1, y);
        dfs(grid, x-1, y);
        dfs(grid, x, y+1);
        dfs(grid, x, y-1);
    }
    int numIslands(vector<vector<char>>& grid) 
    {
        int island = 0;
        int n = grid.size();
        int m = grid[0].size();
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(grid[i][j] == '1')
                {
                    island++;
                    dfs(grid, i, j);
                }
            }
        }
        return island;
    }
};

LC-207课程表 、LC-210课程表II

这两道题涉及的都是图的拓扑排序问题，以及计算图中是否有环。

判断图中是否有环的方法：

1. 拓扑排序

   1. 求出图中所有结点的度。
   2. 将所有度 <= 1 （有向图）=0（无向图）的结点入队。（独立结点的度为 0）
   3. 当队列不空时，弹出队首元素，把与队首元素相邻节点的度减一。如果相邻节点的度变为一，则将相邻结点入队。
   4. 循环结束时判断已经访问的结点数是否等于 n。等于 n 说明全部结点都被访问过，无环；反之，则有环。

2. 深度优先搜索

   使用 DFS 可以判断一个无向图和有向中是否存在环。深度优先遍历图，如果在遍历的过程中，发现某个结点有一条边指向已访问过的结点，并且这个已访问过的结点不是上一步访问的结点，则表示存在环。

   我们不能仅仅使用一个 bool 数组来表示结点是否访问过。规定每个结点都拥有三种状态，白、灰、黑。开始时所有结点都是白色，当访问过某个结点后，该结点变为灰色，当该结点的所有邻接点都访问完，该节点变为黑色。

   那么我们的算法可以表示为：如果在遍历的过程中，发现某个结点有一条边指向灰色节点，并且这个灰色结点不是上一步访问的结点，那么存在环。

3. 并查集

210题的示例如下，是DFS和拓扑排序相结合的方法：

vector<vector<int>> edges;
vector<int> visited;
vector<int> result;
bool valid = true;
void dfs(int u)
{
    visited[u] = 1;
    for(auto v : edges[u])
    {
        if(visited[v] == 0)
        {
            dfs(v);
            if(valid != true)
                return;
        }
        else if(visited[v] == 1)
        {
            valid = false;
            return;
        }
    }
    visited[u] = 2;
    result.push_back(u);
}
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) 
{
    edges.resize(numCourses);
    visited.resize(numCourses);
    for(auto &info : prerequisites)
    {
        edges[info[1]].push_back(info[0]);
    }
    for(int i=0; i<numCourses; i++)
    {
        if(visited[i] == 0)
            dfs(i);
    }
    if(valid == false)
        return {};
    reverse(result.begin(),result.end());
    return result;
}