图论中的一些基础算法，包括最短路、最小生成树、直径、最近公共祖先、拓扑排序和二分图等。

最短路径

单源最短路径

给定一张有向图 $G = (V, E)$ ，$V$ 是点集，$E$ 是边集，$|V| = n$，$|E| = m$，节点以 $[1, n]$ 之间的连续整数编号，$(x, y, z)$ 描述一条从 $x$ 出发，到达 $y$，长度为 $z$ 的有向边。设 1 号节点为起点，求长度为 $n$ 的数组 $dist[1..n]$，其中$dist[i]$ 表示起点1到节点 $i$ 的最短路径长度。

Dijkstra算法

Dijkstra算法基于贪心思想，且只适用于所有边的长度都是非负数的图。

算法流程：

  1. 初始化 $dist[1] = 0$，其余节点的 $dist$ 值为无穷大。
  2. 找一个未被标记的、$dist[x]$ 最小的节点 $x$，然后标记节点 $x$。
  3. 扫描节点 $x$ 的所有出边 $(x, y, z)$，若 $dist[y] > dist[x] + z$，则使用 $dist[x] + z$ 更新 $dist[y]$。
  4. 重复上述 2-3 两个步骤，知道所有节点都被标记。

初始化时 1号节点到自己的距离为0，然后从1号节点出发，1号节点的直接相邻节点中权值最小的一定是可以被确定的。按照这种思想更新所有节点即可求解单源最短路径问题。采用优先队列进行优化，每个节点在第一次出队列时得到最短路径，时间复杂度为 $O((m+n)logn)$ 。

问题

Leetcode-743 Network Delay Time

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Example 1:

img

1
2
Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2

Note:

  1. N will be in the range [1, 100].
  2. K will be in the range [1, N].
  3. The length of times will be in the range [1, 6000].
  4. All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 0 <= w <= 100.

分析

以K为源点求单源最短路径中最大的那个，如果不能全部连通则返回-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
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        vector<vector<pair<int, int>>> e(N+1, vector<pair<int, int>>());
        vector<int> d(N+1, 0x3f3f3f3f);
        vector<int> v(N+1, false);

        for (vector<int> &t: times) {
            e[t[0]].push_back(make_pair(t[1], t[2]));
        }

        priority_queue<pair<int,int>> q;   // -d[x], nodeNum
        q.push(make_pair(0, K));
        d[K] = 0;
        while (q.size()) {
            int x = q.top().second;
            q.pop();
            if (v[x]) continue;
            v[x] = true;

            for (int i = 0; i < e[x].size(); ++i) {
                int y = e[x][i].first, z = e[x][i].second;
                if (d[y] > d[x] + z) {
                    d[y] = d[x] + z;
                    q.push(make_pair(-d[y], y));
                }
            }
        }

        int ans = 0;
        for (int i = 1; i <= N; ++i) {
            if (v[i] == false)
                return -1;
            ans = max(ans, d[i]);
        }
        return ans;
    }
};

Bellman-Ford算法

给定一张有向图，若对于图中某一条边 $(x, y, z)$ ，有 $dist[y] \leq dist[x] + z$ 成立，则称该边满足三角不等式。若所有边都满足三角不等式，则 $dist[]$ 数组就是所求的最短路。

基本思想迭代优化

  1. 扫描所有边 $(x, y, z)$，若 $dist[y] > dist[x] + z$，则用 $dist[x] + z$ 更新 $dist[y]$。
  2. 重复上述步骤，直到没有更新发生。

时间复杂度为$O(nm)$。

队列优化的Bellman-Ford算法（SPFA算法）

  1. 建立一个队列，最初队列只含有一个起点1。
  2. 取出对头元素 $x$，扫描它的所有出边 $(x, y, z)$，若 $dist[y] > dist[x] + z$，则使用 $dist[x] + z$ 更新$dist[y]$。同时，若 $y$ 不在队列中，则把 $y$ 入队。
  3. 重复上述步骤，直到队列为空。

在随机图上运行效率 $O(km)$，$k$ 是一个很小的常数。在一些特殊构造的图上，可能退化为 $O(nm)$。

Bellman-Ford 算法（SPFA算法）可以用来处理有负边存在的图。

注意：Dijkstra使用的是优先队列，SPFA使用的是普通的队列。

任意两点之间的最短路径

Floyd算法

Floyd 算法的时间复杂度为 $O(n^3)$。

设 $D[k, i, j]$ 表示经过 “经过若干个编号不超过 $k$ 的节点” 从 $i$ 到 $j$ 的最短路长度。该问题可划分为两个字问题，经过编号不超过 $k-1$ 的节点从i到j，或者节点 $i$ 经过节点 $k$ 到达节点 $j$。于是有转移方程：
$$
D[k, i, j] = min(D[k-1, i, j], \;D[k-1, i, k]+D[k-1, k, j])
$$
初始值为 $D[0, i, j] = A[i, j]$，假设 $A[i, j]$ 为邻接矩阵，表示节点 $i$ 与节点 $j$ 之间的边的长度。

经过空间压缩的 Floyd 算法如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int d[310][310];

memset(d, 0x3f, sizeof(d));
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++i) {
        d[i][j] = a[i][j];
    }
} 

for (int k = 1; k <= n; ++k) {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}

最小生成树

Kruskal算法

Kruskal 算法总是维护无向图的最小生成森林。在任意时刻，Kruskal 算法从剩余的边中选出一条权值最小的，并且两个端点属于森林中两颗不同的树（不连通）的边，把改边加入生成森林。节点连通性可用并查集维护。时间复杂度为 $O(mlogm)$。 // 感觉是否应该是 $O(mlogn)$。

  1. 建立并查集，每个点为一个单独的集合。
  2. 把所有边按权值从小到大排序，并依次扫描每条边 $(x, y, z)$。
  3. 若 $x, y$ 属于同一集合（在一颗相同的树上）则忽略该边，继续查找下一条。
  4. 否则，合并 $x,y$ 所在的集合，并把 $z$ 累加到答案中。
  5. 所有边扫描完成后，第 4 步中处理过的边就构成最小生成树。

Prim算法

待更新

树的直径

两次BFS求直径

  1. 从任意一个节点出发，通过 BFS 或 DFS 对树进行一次遍历，求出与出发点距离最远的节点，记为 $p$。（若有多个距离最远的点，则任选一个）。
  2. 从节点 $p$ 出发，通过 BFS 或者 DFS 再进行一次遍历，求出与 $p$ 距离最远的节点，记为 $q$。
  3. 从 $p$ 到 $q$ 的路径就是树的一条直径。

证明待补充。

最近公共祖先

树上倍增法

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
42
43
44
45
46
47
48
49
50
51
52
53
int head[MAX_N*2];
int ver[MAX_N*2];
int Next[MAX_N*2];
int tot = 0;

int d[MAX_N*2];
int f[MAX_N][20];

queue<int> q;

void add(int x, int y) {
    ver[++tot] = y;
    Next[tot] = head[x];
    head[x] = tot;
}

void bfs() {
    memset(f, 0, sizeof(f));
    memset(d, 0, sizeof(d));
    q.push(1);
    d[1] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = head[x]; i; i = Next[i]) {
            int y = ver[i];
            if (d[y]) continue;
            d[y] = d[x] + 1;
            f[y][0] = x;
            for (int j = 1; j <= t; ++j) {
                f[y][j] = f[f[y][j-1]][j-1];
            }
            q.push(y);
        }
    }
}

int lca(int x, int y) {
    if (d[x] < d[y])
        swap(x, y);
    for (int i = t; i >= 0; --i) {
        if (d[f[x][i]] >= d[y])
            x = f[x][i];
    }
    if (x == y) return x;
    for (int i = t; i >= 0; --i) {
        if (f[x][i] != f[y][i]) {
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}

拓扑排序

拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。

给定一张DAG，对于该图中每两个顶点 $A, B$，若存在一条路径从 $A$ 到达 $B$，那么在拓扑排序中，顶点 $A$ 一定出现在顶点 $B$ 的前面。另外，在一张图的拓扑排序中，每个顶点出现且仅出现一次。

拓扑排序的思想

拓扑排序的思想：只需要不断选择图中入度为 0 的节点 $x$，将节点 $x$ 加入到拓扑序列中中，从将 $x$ 连向的点的入度减 1。直到 DAG 为空或者当前图中不存在入度为 0 的顶点为止。处理流程如下。

  1. 建立空的拓扑序列 $A$。
  2. 预处理所有点的入度 $deg[i]$，并把所有入度为 0 的点加入到队列中。
  3. 队列中取出队头元素 $x$，将其加入到拓扑序列 $A$ 的末尾。
  4. 对于从 $x$ 出发的每条边 $(x, y)$，把 $deg[y]$ 减 1。若减为 0，则把 $y$ 入队。
  5. 重复 3-4 步，直到队列为空，此时，$A$ 就是要求得的拓扑序列。

拓扑排序也可以用来检测有向图中是否有环，若最后得到的拓扑序列A的大小小于图中所有顶点的数量时，则表明该有向图是存在环的。

欧拉回路

存在欧拉回路的图被称为欧拉图，其判定方式为当且仅当无向图连通，且每个点的度数都是偶数。

二分图

二分图的判定

二分图的判定一般使用采用染色法。尝试用黑白两种颜色标记图中的节点，当一个节点被标记后，它的所有相邻节点应该被标记与它相反的颜色。若标记过程中产生冲突，则说明途中存在奇环（长度为奇数的环），不是二分图。二分图染色一般基于深度优先遍历实现，时间复杂度为 $O(N+M)$。

二分图的最大匹配

匈牙利算法（增广路算法）

尚不能通过官方解释来理解，只能通过“挪”的思想来理解。

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// 棋盘覆盖，有坏点
#define SIZE (106)
bool badPoint[SIZE][SIZE];
int n, m;
int match[SIZE*SIZE];
bool visit[SIZE*SIZE];
vector<int> e[SIZE*SIZE];
vector<vector<int>> dirs = {{0,1}, {0,-1}, {-1,0}, {1,0}};

int dfs(int x) {
    for (int i = 0; i < e[x].size(); ++i) {
        int y = e[x][i];
        if (visit[y]) continue;
        visit[y] = true;
        if (!match[y] || dfs(match[y])) {
            match[y] = x;
            return true;
        }
    }
    return false;
}

int main(int argc, const char * argv[]) {
    freopen("input.txt", "r", stdin);
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    scanf("%d%d", &n, &m);
    memset(badPoint, 0, sizeof(badPoint));

    while (m--) {
        int x, y;
        scanf("%d%d", &x, &y);
        badPoint[x][y] = true;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (badPoint[i][j]) continue;
            for (vector<int> dir: dirs) {
                int x = i + dir[0];
                int y = j + dir[1];
                if (x<1||x>n||y<1||y>n || badPoint[x][y]) continue;
                e[(i-1)*n+j-1].push_back((x-1)*n+y-1);
                e[(x-1)*n+y-1].push_back((i-1)*n+j-1);
            }
        }
    }
    memset(match, 0, sizeof(match));
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if ((i+j)&1) {
                memset(visit, 0, sizeof(visit));
                if (dfs(i*n+j)) ans++;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}
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
42
43
44
45
46
47
// 车的摆放
#define N (206)
#define M (206)

int n, m, t;
bool b[N][M];
vector<int> e[N+M];
int match[N*M];
bool visit[N*M];

bool dfs(int x) {
    for (int i = 0; i<e[x].size(); ++i) {
        int y = e[x][i];
        if (visit[y]) continue;
        visit[y] = true;
        if (!match[y] || dfs(match[y])) {
            match[y] = x;
            return true;
        }
    }
    return false;
}

int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d %d %d", &n, &m, &t);
    memset(b, 0, sizeof(b));
    while (t--) {
        int x, y;
        scanf("%d%d", &x, &y);
        b[x][y] = true;
    }
    for (int i = 0; i<n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (b[i+1][j+1]) continue;
            e[i].push_back(n+j);
            e[n+j].push_back(i);
        }
    }
    int ans = 0;
    for (int i = n; i < n+m; ++i) {
        memset(visit, 0, sizeof(visit));
        if (dfs(i)) ans++;
    }
    printf("%d\n", ans);
    return 0;
}