30.图论基础1

发表于 分类于 ，

图论基础1

优先队列及其底层堆结构原理、最小生成树的 Prim 与 Kruskal 算法、最短路的 Floyd 和 Dijkstra 算法及堆优化版本，以及拓扑排序。

优先队列

优先队列（Priority Queue）：

  1. 每次出队的元素都是队列中优先级最高的元素
  2. 可以自定义元素的优先级比较方式

在C++中，我们可以使用STL的priority_queue来实现优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <queue>
using namespace std;

// 默认是大顶堆（大的元素优先级高）
priority_queue<int> pq;

// 小顶堆（小的元素优先级高）
priority_queue<int, vector<int>, greater<int>> pq;

// 常用操作
pq.push(x);    // 入队
pq.top();      // 获取队首元素（优先级最高的元素）
pq.pop();      // 出队
pq.empty();    // 判断队列是否为空
pq.size();     // 获取队列大小

如果想自定义优先级别,可以定义结构体并重载比较符号

1
2
3
4
5
6
7
8
9
10
11
struct Node {
    int x, y;
    bool operator<(const Node& that) const {
        // 这里定义优先级比较规则
        // 返回 true 表示 this 的优先级低于 that
        // 返回 false 表示 this 的优先级高于或等于 that
        // 这里以 x * y 大的优先级高为例
        return this.x * this.y < that.x * that.y;
    }
}
priority_queue<Node> pq;

底层原理:堆

一个除最后一层都"靠左"外，上面每一层都是"满"的二叉树——完全二叉树

但它不是有序的二叉树，它只保证一个性质：

任意节点的值，都是它作为根的子树的最优值，但和兄弟节点之间大小关系随机，即每个子树都是一个"堆"

回顾完全二叉树：

  • 任意节点 \(i\) 的父节点编号是 \(\lfloor i / 2 \rfloor\)
  • 任意节点 \(i\) 的左子节点编号 \(i * 2\)，右子节点编号 \(i * 2 + 1\)

当一个点s除了自身外，它的子节点都已是堆时，通过这个代码可以把它调整成一个堆

设：

  • 保存这个完全二叉树的数组是a[]
  • 某个节点是s
    • s所有子孙的树都是堆，但s作为根的这棵树还不是堆
  • e是最大节点编号
1
2
3
4
5
6
7
8
9
10
11
12
13
void HeapAdjust(int a[], int s, int e) {
    // 假设在构建 小根 堆，即目标是任意节点都比它所有子孙节点小
    for(int nex = s << 1; nex <= e; nex <<= 1) {
        // nex 指向 s 的左子节点，看 nex 和 nex+1 哪个子节点小，如果右边更小则 nex++ 指向右边
        if(nex + 1 <= e && a[nex + 1] < a[nex]) nex ++; 
        // 如果 a[s] 比 左右子节点都小，由于子树已经是堆了，a[s]又更小，那么已经完成了堆的调整，可退出
        if(a[s] <= a[nex]) break;
        // 否则，将左右子节点较小的与 a[s] 交换，目的是把较大的值往叶子方向换，把较小的"往上提"
        Swap(a[s], a[nex]);
        // s 追着 nex 跑，保持 s 是 nex 父节点
        s = nex;                    
    }
}

以前面的图为例，从编号为 \(6\) 的节点开始，让 s 作为 \(6,5,4,3,2,1\) 的顺序分别执行一次 HeapAdjust ，就让整个完全二叉树成为堆了。

注意这个顺序不能变，不能是 \(1,2,3,4,5,6\) 的顺序，因为对 s 执行 HeapAdjust 的前提是 s 的子孙树们都已经是堆。从\(6\)开始往前来的话，每个点处理之前，就都已经把它的子孙树点处理为堆了。

堆与优先队列

一个堆，它的堆顶元素就是优先队列出队时最优先的元素。

当堆顶（a[1]）离开

  1. 需要有元素补位
  2. 需要让它仍然是一个堆

方法是让最后一个元素 a[e] 补位到 a[1]，然后 e--，此时只有堆顶不符合堆要求，调用一次HeapAdjust就可以了

当加入新元素，

  1. 先把新元素放到数组末尾（a[++ e] = new_val;）
  2. 然后从下往上调整，直到满足堆的性质

这个过程与HeapAdjust相似，只不过方向相反，是从叶子往上去，示例代码仍然以小根堆为例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void HeapInsert(int a[], int &e, int x) {
    // e 是当前堆中最后一个元素的下标
    // 先把新元素放到末尾
    a[++e] = x;
    
    // 从下往上调整
    for(int i = e; i > 1; i >>= 1) {
        // 如果当前节点比父节点更优，则交换
        if(a[i] < a[i >> 1]) { 
            Swap(a[i], a[i >> 1]);
        } else {
            break;  // 已经满足堆的性质，可以退出
        }
    }
}

最小生成树

回顾链式前向星建图

1
2
3
4
5
6
7
8
const int maxn = 1100;      // 最大点数
const int maxm = 110000;    // 最大边数
int first[maxn];    // 每个顶点发出的边的边链表头顶点，可初始化为 -1 
int nex[maxm];      // 同个顶点发出的边的边顶点 next 域
int u[maxm];        // 边的发出顶点
int v[maxm];        // 边的收入顶点
int w[maxm];        // 边的权值
int tp;             // 全局"内存分配""指针"，就是模拟分配内存时，tp从0开始逐个增加

如果不习惯数组式组织数据，写成结构体也可以

1
2
3
4
5
6
7
8
9
struct Edge {
    int nex;
    int u;
    int v;
    int w;
};
Edge e[maxn];
int first[maxn]
int tp;

Prim算法（朴素版）

假设我们需要在 \(n\) 个城市之间建立通信网络。为了确保所有城市都能相互通信，我们需要铺设 \(n-1\) 条线路。

虽然任意两个城市之间都可以铺设线路（总共有 \(\frac{n(n-1)}{2}\) 条可能的线路），但每条线路都有不同的建设成本。我们的目标是选择 \(n-1\) 条线路，使得总成本最小。

Prim算法采用贪心的思想来解决这个问题：

  1. 从任意一个城市开始，将其加入已选城市集合
  2. 在已选城市集合和未选城市集合之间，选择成本最低的线路
  3. 将这条线路连接的新城市加入已选城市集合
  4. 重复步骤2和3，直到所有城市都被选中

这种算法特别适合城市数量较多、线路较密集的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 注释由 AI 生成
const int maxn = 110;                       // 最大城市数量
int g[maxn][maxn];                          // 邻接矩阵，存储城市间的距离
int key[maxn];                              // 每个城市到已选城市集合的最小距离
int fixed[maxn];                            // 标记城市是否已加入生成树
int last[maxn];                             // 记录每个城市是通过哪个城市加入生成树的
int t, n, m, tmpLen, start;                 // t:测试用例数 n:城市数 m:线路数 start:起始城市

int Prim(int start) {                           // Prim算法实现，返回最小生成树的总长度
    int ret = 0;                                // 最小生成树的总长度
    memset(key, 0x3f, sizeof(key));             // 初始化所有城市到已选集合的距离为无穷大
    memset(fixed, 0, sizeof(fixed));            // 初始化所有城市都未加入生成树
    key[start] = 0;                             // 起始城市到已选集合的距离为0
    last[start] = -1;                           // 起始城市没有前驱城市
    
    for(int i = 0; i < n; i++) {                // 循环n次，每次选择一个城市加入生成树
        int minKey = 0x3f3f3f3f;                // 当前未选城市到已选集合的最小距离
        int minKeyNode;                         // 对应的城市编号
        
        for(int j = 0; j < n; j++)              // 遍历所有城市
            if(!fixed[j] && key[j] < minKey) {  // 如果城市未加入生成树且距离更小
                minKey = key[j];                // 更新最小距离
                minKeyNode = j;                 // 记录对应的城市
            }
            
        fixed[minKeyNode] = true;               // 将选中的城市加入生成树
        ret += key[minKeyNode];                 // 累加这条边的长度
        
        for(int j = 0; j < n; j++)              // 更新其他未选城市到已选集合的距离
            if(!fixed[j] && g[minKeyNode][j] != 0 && g[minKeyNode][j] < key[j]) {
                key[j] = g[minKeyNode][j];      // 如果通过新加入的城市距离更短，则更新
                last[j] = minKeyNode;           // 记录是通过哪个城市加入的
            }
    }
    return ret;                                 // 返回最小生成树的总长度
}

\(O(n^2)\)，$n为顶点数。

Kruskal算法

Kruskal算法采用了另一种思路：

  1. 首先将所有可能的线路按照成本从低到高排序
  2. 从成本最低的线路开始，依次检查每条线路
  3. 如果这条线路连接的两个城市还没有通过其他线路连通，就选择这条线路
  4. 重复步骤2和3，直到所有城市都能相互通信

这种算法特别适合城市数量较多、但实际线路较少的情况。

Kruskal算法需要频繁判断两个城市是否已经连通，这正好是并查集的强项。在实现中：

  1. 初始时，每个城市自成一个集合
  2. 当选择一条线路时，将线路连接的两个城市所在的集合合并
  3. 判断两个城市是否连通，只需看它们是否在同一个集合中

并查集通过路径压缩优化，使得查找和合并操作的时间复杂度接近 \(O(1)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 注释由 AI 生成
struct KNode {                                      // 存储边的信息
    int len;                                        // 边的长度
    int s, e;                                       // 边的起点和终点
    bool operator<(const KNode &b) const {          // 重载小于运算符，用于排序
        return len == b.len ? s < b.s : len < b.len;// 长度相同时按起点编号排序
    }
    KNode() {}
    KNode(int l_, int s_, int e_): len(l_), s(s_), e(e_) {} // 构造函数
};

KNode eg[maxn * maxn];                              // 存储所有可能的边
int etp;                                            // 边的数量
int p[maxn];                                        // 并查集数组
int fa(int i) {                                     // 查找i所在集合的代表元素
    return p[i] == i ? i : p[i] = fa(p[i]);        // 路径压缩
}

void Kruskal() {                                    // Kruskal算法实现
    etp = 0;                                        // 初始化边的数量
    for(int i = 0; i < n; i++)                      // 遍历所有城市对
        for(int j = i + 1; j < n; j++)
            if(g[i][j] != 0)                        // 如果两个城市之间有线路
                eg[etp++] = KNode(g[i][j], i, j);   // 将这条边加入数组
    
    sort(eg, eg + etp);                             // 按边的长度排序
    
    for(int i = 0; i < n; i++)                      // 初始化并查集
        p[i] = i;                                   // 每个城市自成一个集合
    
    rtp = 0;                                        // 初始化结果边的数量
    for(int i = 0; i < etp; i++) {                  // 遍历所有边
        if(fa(eg[i].s) == fa(eg[i].e))             // 如果边的两个端点已经在同一个集合中
            continue;                               // 跳过这条边
        
        p[fa(eg[i].s)] = fa(eg[i].e);              // 合并两个集合
        res[rtp][0] = eg[i].s;                      // 记录这条边的起点
        res[rtp][1] = eg[i].e;                      // 记录这条边的终点
        rtp++;                                      // 结果边数加1
    }
}

\(O(mlogm)\)，\(m\)为边数。

最短路

暴力最短路——Floyd

求图中两两之间最短路。

基于动态规划思想的算法:

对于任意两点 \(i\) 和 \(j\) 之间的最短路径,要么是直接相连的边,要么需要经过其他点作为中转。可以枚举所有可能的中转点 \(k\),不断更新 \(i\) 到 \(j\) 的最短距离。

具体来说:

  1. \(d_k(i,j)\) 表示从 i 到 j 路径上编号不超过 k 的最短路长度
  2. 初始状态: \(d_0(i,j) = w(i,j)\)
  3. 状态转移: \(d_k(i,j) = min\{d_{k-1}(i,j), d_{k-1}(i,k) + d_{k-1}(k,j)\}\), 其中 \(1 \leq i,j,k \leq n, i \neq k, j \neq k\)

参考代码

1
2
3
4
5
6
7
int g[maxn][maxn];
void Floyd(int n) {  // 节点范围[1, n]
    for(int k = 1; k <= n; k ++)
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                g[i][j] = min(g[i][k] + g[k][j], g[i][j]);
}

\(O(n^3)\)

例：加速通道

给定一个无向图 \(G=(V,E)\)，其中 \(|V|=n\) 个顶点，\(|E|=m\) 条边。每条边 \(e \in E\) 有一个权重 \(w(e)\) 表示通过该边所需时间。

现在可以选择一条边 \(e\)，将其权重变为 \(\lfloor \frac{w(e)}{2} \rfloor\)。求从顶点 \(1\) 到顶点 \(n\) 的最短路径长度。

输入： - 不超过 \(50\) 组测试数据 - 每组第一行两个整数 \(n,m\)，表示顶点数和边数 - 接下来 \(m\) 行，每行三个整数 \(s,e,t\)，表示顶点 \(s\) 和 \(e\) 之间有一条权重为 \(t\) 的无向边 - \(2 \leq n \leq 100\)，\(1 \leq m \leq 2000\) - 保证顶点 \(1\) 和 \(n\) 连通

1
2
3
4
5
6
7
8
9
10
11
3 3
1 2 6
2 3 6
1 3 13
5 6
4 3 3
4 5 18
3 4 0
3 5 2
2 3 10
4 1 6

输出：

每组数据输出一个整数，表示安装加速通道后的最短路径长度

1
2
6
5

这是一个稠密图问题（节点少边多），适合用Floyd算法求任意两点间最短路。

对每条边 \(e\)，计算 \(\min\{dist[1][u] + \lfloor \frac{w(e)}{2} \rfloor + dist[v][n]\}\)，其中 \(u,v\) 是边 \(e\) 的两端点，\(dist[i][j]\) 是 \(i\) 到 \(j\) 的最短路。取所有边中的最小值即为答案。

注意:同一对点之间可能有多条边，要保留权值最小的边。时间复杂度O(n³)。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
const int maxn = 1e2 + 10;
int n, m, g[maxn][maxn], orig[maxn][maxn];
void Floyd() {
    for(int k = 1; k <= n; k ++)
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                g[i][j] = std::min(g[i][k] + g[k][j], g[i][j]);
}
int main() {
    int a, b, c;
    while(scanf("%d%d", &n, &m) != EOF && (n || m)) {
        memset(g, 0x0f, sizeof(g));
        while(m --) {
            scanf("%d%d%d", &a, &b, &c);
            g[a][b] = g[b][a] = c;
        }
        memcpy(orig, g, sizeof(g));
        Floyd();
        for(int i = 1; i <= n; i ++) {
            g[i][i] = 0;
        }
        int ans = 0x0f3f3f3f;
        for(int i = 1; i <= n; i ++) {
            for(int j = 1; j <= n; j ++) {
                ans = std::min(ans, g[1][i] + orig[i][j] / 2 + g[j][n]);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

单源最短路——Dijkstra（朴素版）

一个特定的顶点，到一个特定的终点的最短路 —— Dijkstra算法

算法思想类似最小生成树的 Prim

区别：每次优先的顶点不再是连通分量发出的最短边指向的顶点，而是与源点总距离最短的顶点，直到终点是优先点为止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Dijkstra(int start)
{
    memset(dis, 0x3f, sizeof(dis));
    memset(fixed, 0, sizeof(fixed));
    last[start] = -1;
    dis[start] = 0;
    int minDisNode, minDis;
    for(int i = 0; i < n; i ++)
    {
        minDis = INF;
        for(int j = 0; j < n; j ++)
            if(!fixed[j] && dis[j] < minDis) 
                minDisNode = j, minDis = dis[j];
        fixed[minDisNode] = true;
        for(int j = 0; j < n; j ++)
            if(g[minDisNode][j] != 0 && minDis + g[minDisNode][j] < dis[j])
                dis[j] = minDis + g[minDisNode][j], last[j] = minDisNode;
    }
}

\(O(n^2)\)

堆优化的Prim与Dijkstra

  • Prim 每一步要在已选和未选之间找成本最低边
  • Dijkstra 每一步要在未确定距离点中找距离源点最近点

这两件事都可以把待考查集合由优先队列管理，每次快速找到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
typedef pair<int, int> pii; // 预定义数据对，first为结点与起点距离，second为结点编号
void Dijkstra(int start)
{
    // 此处 “, vector<pii>, greater<pii> ” 用于让优先队列构建大顶堆，从而每次出队为最小值
    priority_queue<pii, vector<pii>, greater<pii> > q;
    memset(dis, 0x3f, sizeof(dis)); // 初始化结点与起点距离为无穷大
    dis[start] = 0;                 // 起点距离起点为0
    q.push(pii(0, start));          // 起点放入优先级队列
    last[start] = -1;               // 记录路径，起点的“上一个”为空
    while(!q.empty())
    {
        pii now = q.top();  // 优先级队列队顶用“top”而不用“front”
        q.pop();            // 出队
        // 如果出队结点记录的距离不是最新的距离，则丢弃该出队结点
        if(now.first != dis[now.second]) continue;  
        for(int i = 0; i < n; i ++)
        {
            // 对每个与 now.second 相连接的结点，看是否能更新该结点与起点的距离
            // 能更新则更新后将该结点入队
            if(g[now.second][i] != 0 && now.first + g[now.second][i] < dis[i])
            {
                dis[i] = now.first + g[now.second][i];
                q.push(pii(dis[i], i));
                last[i] = now.second;
            }
        }
    }
}

使用堆优化后的 Prim 算法时间复杂度为 \(O(m\log n)\)，其中 \(n\) 为顶点数，\(m\) 为边数。对于稀疏图（即边数远小于顶点数平方，\(m \ll n^2\)），这个复杂度明显优于朴素 Prim 算法的 \(O(n^2)\) 复杂度。

总的来说，各算法在使用堆优化后的时间复杂度如下：

  • Prim 算法：堆优化前 \(O(n^2)\) ，堆优化后 \(O(m\log n)\)
  • Dijkstra 算法：堆优化前 \(O(n^2)\) ，堆优化后 \(O((m+n)\log n)\)

效果要看 \(m\) 与 \(n\) 的大小关系，越稀疏（边数少），\(m\)越接近\(n\)，堆优化效果越好；越稠密，\(m\)越接近\(n^2\)，效果就变差了。

拓扑排序

有向无环图简称DAG（directed acycline graph）图，任何点无法通过一系列有向边回到该点，因为无环，顶点就有前后顺序（允许并列）

例：一项工程，有a、b、c、...一系列任务，有的任务必须在其它特定任务完成后才能执行，比如 a 执行后才能开始执行 b，等等一系列规则，假如只能单线程执行任务，在此规则下，给出一个可行的任务执行顺序。

任务执行的先后关系就可以作为有向边，合法的数据不可能出现a->b->c->a的死锁，那就是先有鸡还是先有蛋的问题了，所以工程的任务会建成一个 DAG 图，一个正确的拓扑排序，便是一个可行的任务执行顺序——可以有多种解

入度与出度

对于无向图，一个点发出一条边就是一个度

对于有向图，一个点发出一条边就是一个出度，收入一条边就是一个入度。

1
2
3
4
C-->A-->B
    ^
    |
    D
点 入度 出度
A 2 1
B 1 0
C 0 1
D 0 1

基于入度的拓扑排序算法：以工程例题来说

  • 一个顶点入度为 0 ，则意味着该顶点不需要完成其它任务即可开始
  • 当执行完该任务，则依赖该任务的其它任务都可以减少一个入度——减少了一个依赖
  • 继续寻找入度为 0 的顶点，重复操作直至所有任务执行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void TopoSort()
{
    int i, j, k;
    rtp = 0;
    // 初始化，用于接下来统计入度
    for(i = 0; i < n; i ++) ind[i] = 0;
    for(i = 0; i < n; i ++) 
        for(j = 0; j < n; j ++)
            // g[i][j] 表示存在 i 到 j 的有向边
            ind[j] += g[i][j];
    for(i = 0; i < n; i ++)
    {
        for(j = 0; j < n && ind[j]; j ++);
        // 找到一个入度为 0 的顶点 j
        res[rtp ++] = j;
        ind[j] = -1;  // 标记该顶点已取出
        // 顶点 j 发出的有向边指向的顶点入度都减1
        for(k = 0; k < n; k ++)
            ind[k] -= g[j][k];
    }
}