02 图结构深度优先搜索

深度优先搜索简介

​ 深度优先搜索（depth-first seach，DFS）在搜索到一个新的节点时，立即对该新节点进行遍历；因此遍历需要用先入后出的栈来实现，也可以通过与栈等价的递归来实现。

​ 对于树结构而言，由于总是对新节点调用遍历，因此看起来是向着 深 的方向前进，或者说是垂直方向。考虑如下一颗简单的树，由4 个节点构成共三层，其 DFS 过程如下图所示：

​ 图通常有两种表示方法。假设图中一共有 n 个节点、m 条边。

​ 第一种表示方法是邻接矩阵（adjacency matrix）：我们可以建立一个 n × n 的矩阵 G，如果第 i 个节点连向第 j 个节点，则 G[i][j]= 1，反之为 0；如果图是无向的，则这个矩阵一定是对称矩阵，即 G[i][j] = G[j][i]。

​ 第二种表示方法是邻接链表（adjacency list）：我们可以建立一个大小为 n 的数组，每个位置 i 储存一个数组 或者链表，表示第 i 个节点连向的其它节点。

​ 邻接矩阵空间开销比邻接链表大，但是邻接链表不支持快速查找 i 和 j 是否相连，因此两种表示方法可以根据题目需要适当选择。除此之外，我们也可以直接用一个 m × 2 的矩阵储存所有的边。

547 省份数量 (opens new window)

​ 给定一个二维的 0-1 矩阵，如果第 (i, j) 位置是 1，则表示第 i 城市和第 j 城市相连。已知连接关系是可以传递的，即如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。一组直接或间接相连的城市通同属于一个省份。求一共有多少个省份。

​ 输入是一个二维数组，输出是一个整数，表示省份数量。因为城市连接关系具有对称性，该二维数组为对称矩阵。同时，因为自己与自己相连，对角线上的值全部为 1。

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2

解析：

​ 本题和200 岛屿数量 (opens new window)题本质上是同一道题。

​ 对于题目 200，二维矩阵也是一种图，其表示方法是：每个位置代表一个节点，每个节点与上下左右四个节点相邻。而在本题里面，则是图的邻接矩阵表示：每一行（列）表示一个节点，它的每列（行）表示是否存在一个相邻节点。

​ 因此题目 200 拥有 m × n 个节点，每个节点有 4 条边；而本题拥有 n 个节点，每个节点最多有 n 条边，表示和所有城市都相连，最少可以有 1 条边，表示自己与自己相连。所以这道题与题目 200 本质上是同一道题：搜索图中省份数量和搜索二维矩阵中的岛屿数量。

​ 所以我们仍然使用一个主函数和一个辅函数配合解决本题，主函数用于遍历所有的搜索位置，判断是否满足开始搜索的条件，如果可以即在辅函数中进行搜索。与二维数组情况不同的是，在主函数中我们要设置一个数组用于记录节点（城市）是否已经被访问过；辅函数中我们不再仅仅四向遍历而是要搜索所有与当前节点相连的节点，并递归搜索所有相连的点。

class Solution {
public:
    void dfs(vector<vector<int>>& isConnected, int i, vector<bool>& visited){
        if(visited[i]) return;
        visited[i] = true;
        for(int j=0;j<visited.size();++j){
            if(isConnected[i][j]==1 && !visited[j]){
                dfs(isConnected,j,visited);
            }
        }
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        if(isConnected.empty() || isConnected[0].empty()){
            return 0;
        }
        vector<bool> visited(isConnected.size(),false);
        int ans = 0;
        for(int i=0;i<visited.size();++i){
            if(!visited[i]){
                dfs(isConnected,i,visited);
                ++ans;
            }
        }
        return ans;
    }
};