深度优先搜索

深度优先搜索具体操作是在得到一个新节点时立即遍历该新节点相邻的节点, 这样又得到一个新节点, 同理. 需要注意的是, 遍历过的节点不能被再次遍历. 如下:

从节点 0 出发开始遍历, 得到到新节点 6 时, 立马对新节点 6 进行遍历, 得到新节点 4; 如此反复以这种方式遍历新节点, 直到没有新节点了, 此时返回. 返回到根节点 0 的情况是, 继续对根节点 0 进行遍历, 得到新节点 2, 然后继续以上步骤.

从一个节点出发, 使用 DFS 对一个图进行遍历时, 能够遍历到的节点都是从初始节点可达的, DFS 常用来求解这种 可达性 问题.

1. 朋友圈

班上有 N 名学生. 其中有些人是朋友, 有些则不是. 他们的友谊具有是传递性. 如果已知 A 是 B 的朋友, B 是 C 的朋友, 那么我们可以认为 A 也是 C 的朋友. 所谓的朋友圈, 是指所有朋友的集合.

给定一个 N * N 的矩阵 M, 表示班级中学生之间的朋友关系. 如果M[i][j] = 1, 表示已知第 i 个和 j 个学生互为朋友关系, 否则为不知道. 你必须输出所有学生中的已知的朋友圈总数.

我们可以对问题进行抽象, 将这n个人的朋友圈看成若干无权图, 如下所示, 则给定的n * n的矩阵就是这张图的邻接矩阵, 遍历未标记的一个人, dfs其所有朋友并标记这样我们就得到了一个朋友圈; 再遍历另一个未标记的人, dfs其所有朋友这样又得到一个朋友圈, 以此类推来找到已知的朋友圈总数.

        A          D              H
        B        E   F            I
        C          G            J   K

下面使用代码实现 DFS, 需要额外考虑的是:

• 用栈来保存当前节点, 当遍历新节点放入栈后可以立即弹出当前节点继续遍历(可以使用递归栈).
• 和 BFS 一样使用布尔数组标记遍历过得节点, 防止重复遍历.

private int n;
public int findCircleNum(int[][] M) {
    if (M == null || M.length == 0) return 0;
    n = M.length;
    boolean[] visited = new boolean[n]; // 标记当前节点是否访问过
    int cnt = 0; // 当前的朋友圈数
    for (int i = 0; i < n; i++) {
        // 从未标记的节点开始深度优先搜索
        if (visited[i]) continue;
        cnt++; // 朋友圈数加一
        dfs(M, visited, i);
    }

    return cnt;
}

// 深度优先搜索当前节点所有朋友并标记
private void dfs(int[][] matrix, boolean[]visited, int i) {
    if (visited[i]) return;
    visited[i] = true;
    for (int j = 0; j < n; j++) {
        if (matrix[i][j] == 1) {
            dfs(matrix, visited, j);
        }
    }
}

Note: 上述解法是不是标准的dfs模板(标准的dfs模板在这), 但对问题的抽象有助于锻炼你的思维. 若想使用栈的迭代解法, 可以联想树的dfs, 同理.

2. 参考

• Cyc2018-LeetCode题解