【算法与数据结构】回溯算法、贪心算法、动态规划、图论（笔记三）-十、图论

10.1 深度优先搜索

  DFS和BFS的区别：

• 深度优先搜索（Depth First Search， DFS）是沿着一个方向搜索，不到黄河不死心，直到遇到绝境了，搜不下去了，再换方向（回溯）。
• 广度优先搜索（Breadth First Search， BFS）是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索的方向是四面八方的，因此被称为广度优先搜索。

  因为DFS搜索就一个方向，并且需要回溯，所以用递归来实现是最方便的。二叉树遍历的递归法是DFS，而二叉树遍历的迭代法是BFS。

void dfs(参数) {
    处理节点
    dfs(图，选择的节点); // 递归
    回溯，撤销处理结果
}

  回溯算法本质上也是一种DFS过程，DFS搜索过程可以笼统的划分为三步。一是确定输入参数；二是确定终止条件；三是处理目前搜索节点的出发路径。

void dfs(输入参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本节点所连接的其他节点) {
        处理节点;
        dfs(图，选择的节点); // 递归
        回溯，撤销处理结果
    }
}

10.2 广度优先搜索

  如果说深搜是一条路跑到黑然后再回溯的搜索方式，那么广搜就是一圈一圈的搜索过程。广搜的搜索方式就适合解决两个点之间最短路径的问题。因为广搜是从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。

10.3 并查集

  并查集是当我们需要判断两个元素是否在同一个集合里的时候，我们就要想到用并查集。并查集常用来解决连通性问题。并查集有以下两个功能：

• 将两个元素添加到一个集合中。
• 判断两个元素在不在同一个集合。

  设想我们将三个元素A， B，C（都是int类型）放在同一集合，其实就是将三个元素连通在一起。只需要一个一维数组来表示：father[A] = B, father[B] = C，father[C] = C。当我们使用find函数去寻找数组的元素，如果数组元素的根相同，这样就表示A与B与C连通。

// 将v，u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return; // 如果发现根相同，则说明在一个集合，不同两个节点相连直接返回
    father[v] = u;
}

  find函数通过数组下标找到数组元素，一层一层寻根过程，代码如下：

// 并查集里寻根的过程
int find(int u) {
    if (u == father[u]) return u; // 如果根就是自己，直接返回
    else return find(father[u]); // 如果根不是自己，就根据数组下标一层一层向下找
}

  find函数寻根的过程是通过递归的方式，不断获取father数组下标对应的数值，最终找到集合的根。而这很像在一个多叉树中，从叶子节点出发，找到根节点的过程。如果说这颗树的高度很深，每次寻根需要递归很多次。

  而我们的目的是需要知道这些节点在同一个根下就可以，因此让多茶树的叶子节点直接指向根即可，每次寻根只需要一次。

  要实现这样的路径压缩过程，只需要在递归过程中，让father[u]接住 递归函数 find(father[u])的返回结果。这样是让u的父节点直接变成find函数返回的根节点。进一步可以用三元表达式精简代码。

// 并查集里寻根的过程
int find(int u) {
    if (u == father[u]) return u;
    else return father[u] = find(father[u]); // 路径压缩
}

int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]);
}

  同时，father数组初始化的时候要令 father[i] = i，默认指向自己。

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}

  如果通过find函数找到两个元素属于同一个根的话，那么这两个元素就是同一个集合，代码如下：

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

  结合以上加入并查集join、寻根find、初始化init和判断是否同一集合isSame函数，我们就得到一个并查集完整模板：

int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}
// 并查集里寻根的过程
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return ; // 如果发现根相同，则说明在一个集合，不同两个节点已经相连，直接返回
    father[v] = u;
}

  总结下来，并查集主要具有三个功能：

• 1、寻找根节点函数find(int u)，也就是判断这个节点的祖先节点是哪个；
• 2、将两个节点接入到同一集合，join(int u, int v)函数，可以将两个节点连接在同一根节点上；
• 3、判断两个节点是否在同一集合中，使用isSame(int u, int v)函数，就是判断两个节点是不是同一个根节点。

  复杂度分析：

• 时间复杂度：$O(1)$，真实的复杂度在$O(logn)$和$O(1)$之间，且随着查询或者合并操作的增加，时间复杂度越来越趋近于$O(1)$。
• 空间复杂度：$O(n)$， 申请一个father数组。