树与图算法

sdjasj
  2022-02-19 20:31:35 2022-02-19 20:31 撰寫   2023-05-01 10:57:48 2023-05-01 10:57 更新    5.2k 字數  28 分鐘

考的是怎么从题目条件抽象出图(建图)

树与图存储

邻接表（前向星）

1
2
3
4
5
6
7
8
9
10
11
12
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点，e[k]存储箭头指向的点,we[k]存储该边权值
int h[N], e[N], ne[N],we[N] idx;

// 添加一条边a->b z为权值
void add(int a, int b, int z)
{
    we[idx] = z, e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);

对于每个顶点，添加与其相连的边时按照头插法添加,

搜索算法

DFS与BFS

DFS

1
2
3
4
5
6
7
8
9
10
int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size())
{
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

拓扑排序

时间复杂度 O(n+m), 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
bool topsort()
{
    int hh = 0, tt = -1;

    // d[i] 存储点i的入度
    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;

    while (hh <= tt)
    {
        int t = q[hh ++ ];

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }

    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return tt == n - 1;
}

最短路算法

6828_6fb1dd8eda-最短路

朴素dijkstra算法

时间复杂是 O(n2+m), 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
int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

java版本

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
public class Dijkstra {
    static int[][] g = new int[507][507];
    static int[] dist = new int[507];
    static boolean[] st = new boolean[507];
    static int n, m;
    static {
        for (int i = 0; i < 507; i++) {
            Arrays.fill(g[i], 0x3f3f3f3f);
        }
    }
    public static int dijkstra() {
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[1] = 0;
        for (int i = 0; i < n - 1; i++) {
            int t = -1;
            for (int j = 1; j <= n; j++) {
                if (!st[j] && (t == -1 || dist[t] > dist[j])) {
                    t = j;
                }
            }

            for (int j = 1; j <= n; j++) {
                dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
            }
            st[t] = true;
        }
        if (dist[n] == 0x3f3f3f3f) {
            return -1;
        } else {
            return dist[n];
        }
    }
}

堆优化版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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class HeapDijkstra {
    private static final int N = 1000010;
    static int n;
    static int m;
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static int[] h = new int[N];
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int[] we = new int[N];
    static int idx = 0;
    static {
        Arrays.fill(h, -1);
    }
    static void add(int a, int b, int z) {
        we[idx] = z;
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    static int HeapDijkstra() {
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[1] = 0;
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b)->{return a[1]-b[1];});
        heap.offer(new int[] {1, 0});
        while (!heap.isEmpty()) {
            int[] cur = heap.poll();
            int ver = cur[0], distance = cur[1];
            if (st[ver]) {
                continue;
            }
            st[ver] = true;
            for (int i = h[ver]; i != -1; i=ne[i]) {
                int j = e[i];
                if (dist[j] > distance + we[i]) {
                    dist[j] = distance + we[i];
                    heap.offer(new int[] {j, dist[j]});
                }
            }
        }
        if (dist[n] == 0x3f3f3f3f) {
            return -1;
        }
        return dist[n];
    }

floyd算法

时间复杂度是 O(n3), n 表示点数

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//初始化：
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    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]);
}

JAVA

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
import java.util.Scanner;

public class Floyd {
    private static final int N = 211;
    static int n, m, k;
    static int[][] d = new int[N][N];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        k = in.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    d[i][j] = 0;
                } else {
                    d[i][j] = 0x3f3f3f3f;
                }
            }
        }
        while (m-- > 0) {
            int x = in.nextInt(), y = in.nextInt(), z = in.nextInt();
            d[x][y] = Math.min(d[x][y], z);
        }
        floyd();
        while (k-- > 0) {
            int x = in.nextInt(), y = in.nextInt();
            if (d[x][y] > 0x3f3f3f3f >> 1) {
                System.out.println("impossible");
            } else {
                System.out.println(d[x][y]);
            }
        }
    }

    public static void floyd() {
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
    }
}

其实是个动态规划，d[i][j][k]表示从i到j且只经过1~k点的最短路径,d[i][j][k] = min(d[i][j][k - 1], d[i][k][k - 1] + d[k][j][k - 1])，但在第k次循环时d[i][j]被更新不会对其他d[x][y]的更新造成影响，因为如果i不等于k且j不等于k，那么其他的更新不会用到d[i][j]，如果i等于k或者j等于k，那么,d[i][j][k] == d[i][j][k - 1]

应用

传递闭包：

https://www.acwing.com/problem/content/345/

无向图中的最小环：

https://www.acwing.com/activity/content/problem/content/1509/ 

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
61
62
63
64
65
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3 + 3;
int ans = 0x3f3f3f3f;
int n, m;
int g[N][N];
int rec[N][N];
int d[N][N];
int idx =  -1;
vector<int> path;

void get_path(int i, int j) {
    if (g[i][j] == d[i][j]) {
        path.push_back(i);
        return;
    }
    get_path(i, rec[i][j]);
    get_path(rec[i][j], j);
}

int main() {
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    memset(d, 0x3f, sizeof d);
    for (int i = 0; i < m; i++) {
        int u, v, l;
        cin >> u >> v >> l;
        g[u][v] = g[v][u] = min(g[u][v], l);
        d[u][v] = d[v][u] = min(d[u][v], l);
    }
    
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i < k; i++) {
            for (int j =1; j < i; j++) {
                if (ans > (long long)g[i][k] + g[k][j] + d[i][j]) {
                    ans = g[i][k] + g[k][j] + d[i][j];
                    idx = k;
                    path.clear();
                    get_path(i, j);
                    path.push_back(j);
                    path.push_back(k);
                }
            }
        }
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                    rec[i][j] = k;
                }
            }
        }
    }
    if (idx == -1) {
        printf("No solution.\n");
    } else {
        for (int x : path) {
            printf("%d ", x);
        }
    }
    return 0;
}

Bellman-Ford算法

时间复杂度 O(nm), 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
int n, m;       // n表示点数，m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离

struct Edge     // 边，a表示出点，b表示入点，w表示边的权重
{
    int a, b, w;
}edges[M];

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];

Java版本

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
public class BellmanFord {
    static class edge {
        int a, b, w;
        public edge(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
        }
    }
    static int n;
    static int m;
    static int k;
    private static final int N = 507;
    static int[] dist = new int[N];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        k = in.nextInt();
        edge[] edges = new edge[m];
        for (int i = 0; i < m; i++) {
            int x = in.nextInt(), y = in.nextInt(), z = in.nextInt();
            edges[i] = new edge(x, y, z);
        }
        int t = bellmanFord(edges);
        if (t > 0x3f3f3f3f / 2) {
            System.out.println("impossible");
        } else {
            System.out.println(t);
        }
    }

    public static int bellmanFord(edge[] edges) {
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[1] = 0;
        for (int i = 0; i < k; i++) {
            int[] copy = Arrays.copyOf(dist,N);
            for (int j = 0; j < m; j++) {
                int a = edges[j].a, b = edges[j].b, w = edges[j].w;
                dist[b] = Math.min(dist[b], copy[a] + w);
            }
        }
        return dist[n];
    }
}

spfa 算法求最短路（队列优化的Bellman-Ford算法）

关于入队

接下来由que[head]开始拓展，一旦发现新的路线（dst[que[head]]+w[i]）比原来的（dst[son[i]]）优秀就修正，如果vis[son[i]]==false，也就是说son[i]不在队列中，当然就是入队了，但是如果son[i]在队列中，要不要入队呢？显然不需要。但是如果入队了也不会影响答案。为什么不需要入队呢？（可能你的疑问是：在修正后面这个son[i]的时候，可能会更优秀啊？）因为如果son[i]已经在队列中，那么说明以后一定会再从son[i]开始修正，那么问题就是从上一个son[i]之后到这个son[i]之前这一段，会不会导致后面能修正出更优秀的son[i]？显然这不需要考虑，因为如果更优秀，之后还是会重新把son[i]修正/入队的！所以，这个时候son[i]就不要入队，因为入队无疑会浪费时间和空间。

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
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N];     // 存储每个点是否在队列中

// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

Java

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
61
62
63
64
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Spfa {
    static int n;
    static int m;
    private static final int N = 100010;
    static int[] h = new int[N];
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int[] we = new int[N];
    static int idx = 0;
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static {
        Arrays.fill(h, -1);
    }
    static void add(int a, int b, int z) {
        we[idx] = z;
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        while (m-- > 0) {
            int x = in.nextInt(), y = in.nextInt(), z = in.nextInt();
            add(x, y, z);
        }
        int t = spfa();
        if (t > 0x3f3f3f3f / 2) {
            System.out.println("impossible");
        } else {
            System.out.println(t);
        }
    }

    public static int spfa() {
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[1] = 0;
        Queue<Integer> que = new LinkedList<>();
        que.offer(1);
        while (!que.isEmpty()) {
            int t = que.poll();
            st[t] = false;
            for (int i = h[t]; i != -1; i = ne[i]) {
                int b = e[i];
                if (dist[b] > dist[t] + we[i]) {
                    dist[b] = dist[t] + we[i];
                    if (!st[b]) {
                        st[b] = true;
                        que.offer(b);
                    }
                }
            }
        }
        return dist[n];
    }
}

spfa判断图中是否存在负环

时间复杂度是 O(nm),n 表示点数，m 表示边数

C++

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
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N], cnt[N];        // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N];     // 存储每个点是否在队列中

// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
    // 不需要初始化dist数组
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。

    queue<int> q;
    for (int i = 1; i <= n; i ++ )
    {
        q.push(i);
        st[i] = true;
    }

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;       // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

JAVA

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
61
62
63
64
65
66
67
68
69
70
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class SpfaMinWay {
    static int n;
    static int m;
    private static final int N = 100010;
    static int[] h = new int[N];
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int[] we = new int[N];
    static int idx = 0;
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static int[] count = new int[N];
    static {
        Arrays.fill(h, -1);
    }
    static void add(int a, int b, int z) {
        we[idx] = z;
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        while (m-- > 0) {
            int x = in.nextInt(), y = in.nextInt(), z = in.nextInt();
            add(x, y, z);
        }
        if (spfa()) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }

    public static boolean spfa() {
        Arrays.fill(dist, 0x3f3f3f3f);
        Queue<Integer> que = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            que.offer(i);
            st[i] = true;
        }
        while (!que.isEmpty()) {
            int t = que.poll();
            st[t] = false;
            for (int i = h[t]; i != -1; i = ne[i]) {
                int b = e[i];
                if (dist[b] > dist[t] + we[i]) {
                    dist[b] = dist[t] + we[i];
                    count[b] = count[t]+1;
                    if (count[b] >= n) {
                        return true;
                    }
                    if (!st[b]) {
                        st[b] = true;
                        que.offer(b);
                    }
                }
            }
        }
        return false;
    }
}

判断正环和判断负环类似

https://blog.51cto.com/u_15067244/3900260

生成树

朴素版prim算法

时间复杂度是 O(n2+m), n表示点数，m表示边数

C++

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
int n;      // n表示点数
int g[N][N];        // 邻接矩阵，存储所有边
int dist[N];        // 存储其他点到当前最小生成树的距离
bool st[N];     // 存储每个点是否已经在生成树中


// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
    memset(dist, 0x3f, sizeof dist);

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF) return INF;

        if (i) res += dist[t];
        st[t] = true;

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

JAVA

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
import java.util.Arrays;
import java.util.Scanner;

public class Prim {
    static int n,m;
    private static final int N = 510;
    static int[][] g = new int[N][N];
    static int res;
    static boolean[] st = new boolean[N];
    static int[] dist = new int[N];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        for (int i = 1; i <= n; i++) {
            Arrays.fill(g[i], 0x3f3f3f3f);
        }
        while (m-- > 0) {
            int x = in.nextInt(), y = in.nextInt(), z = in.nextInt();
            g[x][y] = g[y][x] =  Math.min(g[x][y], z);
        }
        int t = prim();
        if (t == 0x3f3f3f3f) {
            System.out.println("impossible");
        } else {
            System.out.println(t);
        }
    }

    public static int prim() {
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[1] = 0;
        for (int i = 0; i < n - 1; i++) {
            int t = -1;
            for (int j = 1; j <= n; j++) {
                if (!st[j] && (t == -1 || dist[t] > dist[j])) {
                    t = j;
                }
            }
            st[t] = true;
            if (dist[t] == 0x3f3f3f3f) {
                return dist[t];
            }
            res += dist[t];
            for (int j = 1; j <= n; j++) {
                dist[j] = Math.min(dist[j], g[t][j]);
            }
        }
        return res;
    }
}

Kruskal算法

时间复杂度是 O(mlogm), n表示点数，m表示边数

C++

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
int n, m;       // n是点数，m是边数
int p[N];       // 并查集的父节点数组

struct Edge     // 存储边
{
    int a, b, w;

    bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edges[M];

int find(int x)     // 并查集核心操作
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    sort(edges, edges + m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if (a != b)     // 如果两个连通块不连通，则将这两个连通块合并
        {
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }

    if (cnt < n - 1) return INF;
    return res;
}

JAVA

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
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int n, m;
    static int N = 100010;
    private static final int M = 200010;
    static int[] p = new int[N];
    static int[][] edge = new int[M][3];
    static int cnt = 0;
    static int res = 0;

    public static int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        for (int i = 0; i < m; i++) {
            int x = in.nextInt(), y = in.nextInt(), w = in.nextInt();
            edge[i] = new int[] {x, y, w};
        }
        int[] ans = kruskal();
        if (ans[0] < n - 1) {
            System.out.println("impossible");
        } else {
            System.out.println(ans[1]);
        }
    }

    public static int[] kruskal() {
        Arrays.sort(edge, 0, m, (a, b) -> a[2] - b[2]);
        for (int i = 1; i <= n; i++) {
            p[i] = i;
        }
        for (int i = 0; i < m; i++) {
            int a = edge[i][0], b = edge[i][1], w = edge[i][2];
            a = find(a);
            b = find(b);
            if (a != b) {
                p[a] = b;
                cnt++;
                res += w;
            }
        }
        return new int[] {cnt, res};
    }
}

二分图

二分图当且仅当图中不含有奇数环

二分图中最小点覆盖个数 == 最大匹配数 == 点的总数 - 最大独立集个数

染色法判别二分图

C++

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
int n;      // n表示点数
int h[N], e[M], ne[M], idx;     // 邻接表存储图
int color[N];       // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色

// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c)
{
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (color[j] == -1)
        {
            if (!dfs(j, !c)) return false;
        }
        else if (color[j] == c) return false;
    }

    return true;
}

bool check()
{
    memset(color, -1, sizeof color);
    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (color[i] == -1)
            if (!dfs(i, 0))
            {
                flag = false;
                break;
            }
    return flag;
}

JAVA

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
import java.util.Arrays;
import java.util.Scanner;

public class erfentuRanSe {
    static int n, m;
    private static final int N = 200010;
    static int[] e = new int[N];
    static int[] h = new int[N];
    static int[] ne = new int[N];
    static int idx = 0;
    static int[] color = new int[N];
    static {
        Arrays.fill(h, -1);
        Arrays.fill(color, -1);
    }

    static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    public static boolean dfs(int a, int col) {
        color[a] = col;
        for (int i = h[a]; i != -1; i = ne[i]) {
            int j = e[i];
            if (color[j] == -1) {
                if (!dfs(j, col == 0 ? 1 : 0)) {
                    return false;
                }
            } else if (color[j] == col){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        for (int i = 0; i < m; i++) {
            int x = in.nextInt(), y = in.nextInt();
            add(x, y);
            add(y, x);
        }
        boolean flag = true;
        for (int i = 1; i <= n; i++) {
            if (color[i]==-1 && !dfs(i, 0)) {
                flag = false;
                break;
            }
        }
        if (flag) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

二分图最大匹配

匈牙利算法

时间复杂度是 O(nm), n表示点数，m表示边数

C++

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
int n1, n2;     // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx;     // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N];       // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N];     // 表示第二个集合中的每个点是否已经被遍历过

bool find(int x)
{
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true;
            if (match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }

    return false;
}

// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ )
{
    memset(st, false, sizeof st);
    if (find(i)) res ++ ;
}

JAVA

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
import java.util.Arrays;
import java.util.Scanner;

public class Hungarian {
    static int N = 510;
    static int M = 100010;
    static int n1;
    static int n2;
    static int m;
    static int idx = 0;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int[] match = new int[N];
    static boolean[] st = new boolean[N];
    static {
        Arrays.fill(h, -1);
    }

    static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    static boolean find(int x) {
        for (int i = h[x]; i != -1; i = ne[i]) {
            int j = e[i];
            if (!st[j]) {
                st[j] = true;
                if (match[j] == 0 || find(match[j])) {
                    match[j] = x;
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n1 = in.nextInt();
        n2 = in.nextInt();
        m = in.nextInt();
        while (m-- > 0) {
            int a = in.nextInt(), b = in.nextInt();
            add(a, b);
        }
        int res = 0;
        for (int i = 1; i <= n1; i++) {
            Arrays.fill(st, false);
            if (find(i)) {
                res++;
            }
        }
        System.out.println(res);
    }
}

Tarjan算法

割点：把这个点及与其相连的边删除后的图的极大连通分量增加的点

割边：把这条边删除后图的极大连通分量增加的边

  • 標題: 树与图算法
  • 作者: sdjasj
  • 撰寫于: 2022-02-19 20:31:35
  • 更新于: 2023-05-01 10:57:48
  • 連結: https://redefine.ohevan.com/2022/02/19/树与图算法/
  • 版權宣告: 本作品采用 CC BY-NC-SA 4.0 进行许可。
 留言
此頁目錄
树与图算法
  1. 树与图存储
    1. 邻接表（前向星）
  2. 搜索算法
    1. DFS与BFS
      1. DFS
      2. BFS
  3. 拓扑排序
  4. 最短路算法
    1. 朴素dijkstra算法
      1. 堆优化版dijkstra
    2. floyd算法
      1. 应用
    3. Bellman-Ford算法
    4. spfa 算法求最短路（队列优化的Bellman-Ford算法）
    5. spfa判断图中是否存在负环
  5. 生成树
    1. 朴素版prim算法
    2. Kruskal算法
  6. 二分图
    1. 染色法判别二分图
    2. 二分图最大匹配
      1. 匈牙利算法
  7. Tarjan算法