代码随想录一刷笔记_图论

60+在408的算法考察难度和深度上还是收手了👍）

图论理论基础

DFS & BFS

• 广度优先适用于解决寻找两个点之间的最短路径问题（不管是否有障碍，第一条到达终点的路径一定是最短路径！）
  • 关于BFS存储元素的容器的选择
    • 用队列的话，就是保证每一圈都是一个方向去转，例如统一顺时针或者逆时针
    • 用栈的话，就是第一圈顺时针遍历，第二圈逆时针遍历，第三圈有顺时针遍历！！

并查集

• 并查集处理的问题：查询（Find） & 合并（Union）

• 并查集的两种思想

  • quick-find

    根据id判断是否属于同一堆

  • quick-union⭐⭐⭐

    使用parent数组记录父节点

    两种合并方法：

    • 按秩合并

      • 按size合并

        结点总数较小的树指向结点数较多的

      • 按rank合并

        高度较小的树指向高度较高的

    • 路径压缩

      • 隔代压缩

        两步一跳，一直循环执行「把当前结点指向它的父亲结点的父亲结点」这样的操作

      • 完全压缩

        把从「查询结点」到「根结点」沿途经过的所有结点都指向根结点。「隔代压缩」相比较于「完全压缩」，压缩彻底

最小生成树

• kruskal

  算法的步骤：

  1. 所有边从小到大排序；
  2. 依次加入最小生成树中，如果形成环则跳过；
  3. 直到选择N-1条边为止。

• prim

  将顶点分为两组：分别为已访问和没访问。

  初始，从未访问组中随机挑一个点放入已访问组；

  选择最短的一条边（两个顶点分别为已访问的和未访问的），将这个未访问顶点放入已访问组中；

  重复n - 1次。

797 所有可能的路径

dfs

使用回溯方法递归。

bfs

借助栈，广度遍历当前顶点的每一条边。

如果指向的顶点为终点，则存入输出数组，反之压入栈中。

200 岛屿数量

首先呢，岛屿只能通过四个方向连接起来，也就是“上”、“下”、“左”、“右”。

dfs

因为是深搜，所以得先朝一个方向搜索到底，碰壁后再换个方向搜索。

这一题除了存储岛屿的数组以外，还定义了一个数组用于存储是否已经遍历过该岛屿，需要通过深搜得到的新岛屿是否与原岛屿连接并且没有被遍历过两个条件进行判断。

bfs

使用广度优先，就需要按照层次遍历当前岛屿周围的岛，那么，就需要一个容器来存储周围层次的岛屿了。

另外，为了避免重复遍历岛屿，当岛屿加入队列时，就需要进行标记；这样一来就不会出现重复入队的情况。

105 岛屿的最大面积

这一题就是105的变式，稍微修改一下即可。

11 建造最大岛屿

暴力解法

遍历一遍空岛屿，每次都查询一下最大的岛屿面积。

时间复杂度为 O(n4)

改进一下的方法（仔细想了以下似乎行不通）

1. 找到当前最大的岛屿
2. 遍历这个岛屿周围的一圈空岛屿，记录最大岛屿的情况

如果这个大岛屿是个孤岛的话就麻烦了x

较优解

1. 还是遍历一遍岛屿，将相连的岛屿进行标记，并记录下这个标记对应的岛屿面积

   例如，统一标记为一个数值。

2. 遍历海域，计算当前海域相邻的岛屿面积 + 1 的值，取最大值。

时间复杂度为 O(n2)。

110 字符串接龙

这一题的话是要通过一系列的步骤将初始的字符串变为结果的字符串，每次只能改一个字符。由于是要求最短路径，所以广搜更贴合要求。

990 等式方程的可满足性

这一题很明显可以用并查集来解。

然后我想用一次循环解决问题，写了下面的代码，显示测试失败：

for (const string& str: equations) {
    int index1 = str[0] - 'a';
    int index2 = str[3] - 'a';

    if (str[1] == '=') {
        uf.unite(index1, index2);
    } else {
        if (uf.find(index1) == uf.find(index2)) return false;
    }
}

模拟一下，如果是按照a!=b a==b的序列出现，最后会返回true。并查集只有“合并”和“查找”两个操作，所以得遍历两次才能避免上述例子这样的错误出现。

547 省份数量

这一题只需要使用并查集的合并方法即可。省份数量只需比较index == city[index]。

684 冗余连接

众所周知，n个顶点最少只要 n - 1 条线就可以形成连通图，所以，这一题是要找多出的一条关系。

难点在测试数据的顺序上：当按照顺序形成两团并查集的时候，当一个并查集的子节点连向另一个并查集的根的时候，当前并查集的根节点需要额外处理（连向新并查集的根节点）。在改变根节点后，通过判断两个节点的根节点是否在同一棵树上就可以说明当前的关系是否是冗余的（没必要把所有结点都遍历一遍）。

1319 连通网络的操作次数

这题与684 冗余连接类似。

765 情侣牵手

可以将可能分为三种情况：

1. 一对情侣已经牵手成功；
2. 两对情侣互相交换即可牵手成功；
3. 三对情侣互相交换即可牵手成功。

这三种情况分别对应的交换次数为 0，1，2。

也就是说：最少交换次数=情侣对数-1

将三种情况抽象成连通分量，也就是说交换之后的连通分量个数 - 交换之前的连通分量个数 = 最少的交换次数。

交换之后的连通分量个数显然就是沙发的个数（也就是情侣数），那么该如何算交换之前的连通分量个数呢？

可以使用并查集的思想，将目前坐在同一沙发上的人放在一个集合中，计算统共有多少组连通分量即可。

1584 连接所有点的最小费用

这是一个求最小生成树的题。

kruskal

主要问题在于如何使用代码实现？

可以分为三个步骤：

1. 存储两个顶点坐标以及顶点间的距离；

   使用二维数组的方法存储（按照距离，顶点1坐标，顶点2坐标的格式）。

2. 按照顶点距离排序；

3. 使用并查集合并未并入的顶点。

   合并结束条件：当选择n - 1条边时。

prim

使用这个方法只需要维护一个最短距离数组即可~

每当加入一个新的顶点，需要进行以下操作：

• 将已加入顶点之间的距离置为INT_MAX；
• 遍历未加入顶点和新加入顶点间的距离，如果距离比存储值更短，则进行替换。