Yuxuan Lin
写作

图论

笔记，编程与算法 / 算法与题解4 分钟阅读

邻接矩阵

邻接矩阵的优点：

  • 表达方式简单，易于理解
  • 检查任意两个顶点间是否存在边的操作非常快
  • 适合稠密图，在边数接近顶点数平方的图中，邻接矩阵是一种空间效率较高的表示方法。

缺点：

  • 遇到稀疏图，会导致申请过大的二维数组造成空间浪费 且遍历 边 的时候需要遍历整个n * n矩阵，造成时间浪费

邻接表

邻接表的优点：

  • 对于稀疏图的存储，只需要存储边，空间利用率高
  • 遍历节点连接情况相对容易

缺点：

  • 检查任意两个节点间是否存在边，效率相对低，需要 O(V)时间，V表示某节点连接其他节点的数量。
  • 实现相对复杂，不易理解

104.建造最大岛屿

直接给岛编号（mark+=1），并维护一个 编号-面积 的list

106.岛屿的周长

岛屿问题最容易让人想到BFS或者DFS，但 106.岛屿的周长 确实还用不上

110.字符串接龙

  • 本题是一个无向图，需要用标记位，标记着节点是否走过，否则就会死循环！
  • 使用set来检查字符串是否出现在字符串集合里更快一些

在无权图中，用广搜求最短路最为合适，广搜只要搜到了终点，那么一定是最短的路径。

并查集

并查集常用来解决连通性问题。

大白话就是当我们需要判断两个元素是否在同一个集合里的时候，我们就要想到用并查集。

并查集主要有两个功能：

  • 将两个元素添加到一个集合中。
  • 判断两个元素在不在同一个集合
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;
}

并查集只能加边，遇到删边的情况，可以考虑逆序操作

399.除法求值

加权并查集

prim

prim算法核心就是三步，我称为prim三部曲，大家一定要熟悉这三步，代码相对会好些很多：

  1. 第一步，选距离生成树最近节点
  2. 第二步，最近节点加入生成树
  3. 第三步，更新非生成树节点到生成树的距离（即更新minDist数组）

kruscal的思路：

  • 边的权值排序，因为要优先选最小的边加入到生成树里
  • 遍历排序后的边
    • 如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
    • 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合

Kruskal 与 prim 的关键区别在于，prim维护的是节点的集合，而 Kruskal 维护的是边的集合。 如果 一个图中，节点多，但边相对较少，那么使用Kruskal 更优。

为什么边少的话，使用 Kruskal 更优呢？

因为 Kruskal 是对边进行排序的后 进行操作是否加入到最小生成树。

边如果少，那么遍历操作的次数就少。

在节点数量固定的情况下，图中的边越少，Kruskal 需要遍历的边也就越少。

而 prim 算法是对节点进行操作的，节点数量越少，prim算法效率就越优。

所以在 稀疏图中，用Kruskal更优。 在稠密图中，用prim算法更优。

边数量较少为稀疏图，接近或等于完全图（所有节点皆相连）为稠密图

Prim 算法 时间复杂度为 O(n^2)，其中 n 为节点数量，它的运行效率和图中边树无关，适用稠密图。

Kruskal算法 时间复杂度 为 nlogn，其中n 为边的数量，适用稀疏图。

拓扑排序

BFS + 入度

Dijkstra

Dijkstra三部曲：

  1. 第一步，选源点到哪个节点近且该节点未被访问过
  2. 第二步，该最近节点被标记访问过
  3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）

需要注意两点：

  • dijkstra 算法可以同时求 起点到所有节点的最短路径
  • 权值不能为负数

Bellman & Ford

对所有边松弛 n-1 次，然后得出得到终点的最短路径

  • 时间复杂度： O(N * E) , N为节点数量，E为图中边的数量
  • 空间复杂度： O(N) ，即 minDist 数组所开辟的空间

（没有负权回路） 队列优化 SPFA算法（Shortest Path Faster Algorithm） 如果图越稠密，则 SPFA的效率越接近与 Bellman_ford SPFA 在最坏的情况下是 O(N * E)，但 一般情况下 时间复杂度为 O(K * N)，K 为不定值

有负权回路: 无限松弛 -> 无限最短路径 检测：n-1 基础上，再多松弛一次，看minDist数组 是否发生变化