图论#

图论基础#

无论无向图还是有向图一般用vector<vector<int>> g; g.resize(n + 1, vector<int>()); 多源最短路径的时候用邻接矩阵，只有树的建图是特殊的树就是无环连通图，无环图就是森林

连通且无环
连通且边数为 n−1，防止孤立点导致剩下的有环
无环且边数为 n−1，防止孤立点导致不连通
任意两个顶点之间有且仅有一条简单路径

Huffman树#

最小的值放越下面，越大越接近根结点取两个值最小的结点放最下面并形成根节点为其和

AOE网及关键路径#

//TODO

回溯#

循环可能的取值时对可能的取值进行判断和初始化相关控制变量，并在最开始的时候特判和初始化相关控制变量，如果进去说明判断成功，故终止条件是实指针

最短路#

单源最短路径#

朴素Dijkstra是初始化确认源点并松弛其出边, 然后每次确认尚未确认的点中dist最小的点并松弛其出边，堆优化Dijkstra是优先队列BFS，Bellman-ford是n次松弛通过出度松弛dist

Dijkstra#

设：

当前从堆里取出的点是 u
此时 dist[u] 是所有未确定点中最小的

假设 存在一条更短的路径： s → ... → x → ... → u，长度 < dist[u]

其中：

x 是这条路径上 第一个尚未被确定的点
x 之前的点都已经被确定了

那么：

到 x 的真实最短距离
$dist(x) \le \text{真实路径到 } u < dist[u]$
而 Dijkstra 一定已经在处理 x 的前驱时：
- 尝试过松弛 x
- 所以 dist[x] 应该已经 ≤ 这个真实最短值
于是得到：
$dist[x] < dist[u]$
矛盾出现了
- 既然 dist[x] < dist[u]
- 那 x 应该比 u 更早从堆里弹出
- 不可能轮到 u

简而言之，假设a+b<c，b > 0，则有a < c - b < c，与 c < a矛盾，故不需比对已经确认的点，可以将最短遍历路上的其他点标为确认，dijkstra每次选最短的边是从已经遍历的点的所有出边里面选，可看作为小根堆，扩展了则出边出堆。

朴素

1
// 朴素Dijkstra
2
int dijkstra(int s, int n) {
3
    memset(dist, 0x3f, sizeof dist);
4
    dist[s] = 0;
5

6
    for (int k = 0; k < n - 1; ++k) {
7
        int t = 0;
8
        for (int i = 1; i <= n; ++i) if (!st[i] && (!t || dist[i] < dist[t])) t = i;
9
        for (int i = 1; i <= n; ++i) dist[i] = min(dist[i], dist[t] + g[t][i]);
10
        st[t] = 1;
11
    }
12

13
    return dist[n] == INF ? -1 : dist[n];
14
}

堆优化

1
// 堆优化Dijkstra
2
int Dijkstra(int s, int n) {
3
    memset(dist, 0x3f, sizeof dist);
4
    dist[s] = 0;
5

6
    priority_queue<PII, vector<PII>, greater<PII>> q;
7
    q.push({0, s});
8

9
    while(q.size()) {
10
        PII t = q.top();
11
        int ver = t.second, dis = t.first;
12
        if (st[ver]) continue;st[ver] = 1;
13

14
        for (int i = h[ver]; i != -1; i = ne[i]) {
15
            int j = e[i];
16
            if (dist[j] > dist[ver] + w[i]) {
17
                dist[j] = dist[ver] + w[i];
18
                q.push({dist[j], j});
19
            }
20
        }
21
    }
22

23
    return dist[n] == INF ? -1 : dist[n];
24
}

Bellmanford#

1
// Bellmanford
2
int Bellmanford(int s, int n, int m) {
3
    memset(dist, 0x3f, sizeof dist);
4
    dist[s] = 0;
5

6
    for (int k = 0; k < n; ++k) {
7
        for (int i = 1; i <= n; ++i) {
8
            int a = i;
9
            for (int j = h[i]; j != -1; j = ne[j]) {
10
                int b = e[j];
11
                dist[b] = min(dist[b], dist[a] + w[i]);
12
            }
13
        }
14
    }
15

16
    return dist[n] > dist[n] >> 1 ? -1 : dist[n];
17
}

任意两点最短路径#

Floyd#

适合稠密图找任意两点的最短路径

1
void floyd(int n) {
2
    for (int k = 1; k <= n; ++k) {
3
        for (int i = 1; i <= n; ++i) {
4
            for (int j = 1; j <= n; ++j) {
5
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
6
            }
7
        }
8
    }
9
}

最小生成树#

Prim#

找未遍历过的最近点

Kruscal#

找最短的连接不同连通分量的边

至多 m - 2 次就能合并成功

BFS#

多源BFS#

多源BFS能遍历所有点的最小步骤数量取决于图里最长的一条路径，步数等于路径长度

DFS#

自顶向下的DFS为回溯
自底向上的DFS为DP 两种方向可以同时存在，因为这个方向说的是DFS函数帧里的参数，包括使用到的全局变量和函数参数

Tarjan#

求强连通分量#

1
const int N = 100005;
2

3
vector<int> g[N];
4

5
int dfn[N], low[N], timestamp;
6
int stk[N], top;
7
bool in_stk[N];
8

9
int scc_id[N], scc_cnt;
10

11
void tarjan(int u) {
12
    dfn[u] = low[u] = ++timestamp;
13
    stk[++top] = u;
14
    in_stk[u] = true;
15

16
    for (int v : g[u]) {
17
        if (!dfn[v]) {
18
            tarjan(v);
19
            low[u] = min(low[u], low[v]);
20
        }
21
        else if (in_stk[v]) {
22
            low[u] = min(low[u], dfn[v]);
23
        }
24
    }
25

26
    // 找到一个 SCC
27
    if (dfn[u] == low[u]) {
28
        ++scc_cnt;
29
        int y;
30
        do {
31
            y = stk[top--];
32
            in_stk[y] = false;
33
            scc_id[y] = scc_cnt;
34
        } while (y != u);
35
    }
36
}

Tarjan 求割点（无向图）#

1
vector<int> g[N];
2
int dfn[N], low[N], timestamp;
3
bool is_cut[N];
4

5
void tarjan(int u, int parent) {
6
    dfn[u] = low[u] = ++timestamp;
7

8
    int child = 0;
9

10
    for (int v : g[u]) {
11
        if (!dfn[v]) {
12
            tarjan(v, u);
13
            low[u] = min(low[u], low[v]);
14

15
            // 割点判断
16
            if (parent != -1 && low[v] >= dfn[u])
17
                is_cut[u] = true;
18

19
            child++;
20
        }
21
        else if (v != parent) {
22
            low[u] = min(low[u], dfn[v]);
23
        }
24
    }
25

26
    // 根节点特殊判断
27
    if (parent == -1 && child > 1)
28
        is_cut[u] = true;
29
}

求桥#

1
struct Edge {
2
    int to, id;
3
};
4

5
vector<Edge> g[N];
6
int dfn[N], low[N], timestamp;
7
bool is_bridge[N];
8

9
void tarjan(int u, int in_edge) {
10
    dfn[u] = low[u] = ++timestamp;
11

12
    for (auto [v, id] : g[u]) {
13
        if (!dfn[v]) {
14
            tarjan(v, id);
15
            low[u] = min(low[u], low[v]);
16

17
            //  桥判断
18
            if (low[v] > dfn[u])
19
                is_bridge[id] = true;
20
        }
21
        else if (id != in_edge) {
22
            low[u] = min(low[u], dfn[v]);
23
        }
24
    }
25
}

音乐

音乐

图论#

图论基础#

Huffman树#

AOE网及关键路径#

回溯#

最短路#

单源最短路径#

Dijkstra#

Bellmanford#

任意两点最短路径#

Floyd#

最小生成树#

Prim#

Kruscal#

BFS#

多源BFS#

DFS#

Tarjan#

求强连通分量#

Tarjan 求割点（无向图）#

求桥#

文章分享

评论区

音乐

目录

音乐

音乐

9-图论

图论#

图论基础#

Huffman树#

AOE网及关键路径#

回溯#

最短路#

单源最短路径#

Dijkstra#

Bellmanford#

任意两点最短路径#

Floyd#

最小生成树#

Prim#

Kruscal#

BFS#

多源BFS#

DFS#

Tarjan#

求强连通分量#

Tarjan 求割点（无向图）#

求桥#

文章分享

评论区

音乐

目录