模板-图论

发表于 更新于 分类于

邻接表存图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int h[N], ne[M], e[M], idx = 0;
// h[i] 指向节点i的第一个边，ne[i]为边i的下一条边，e[i]为边i的目标节点
void init()
{
    memset(h, -1, sizeof(h));
}

void add(int u, int v)
{
    e[idx] = v;
    ne[idx] = h[u];
    h[u] = idx++;
}

void do_something_to_all_adjacent_side(int u)
{
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        do_something(v);
    }
}

拓补排序

将所有入度为0的节点入队。每次入队时，更新相邻节点的度数，并判断跟新后是否为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
vector<int> topo;

bool topsort()
{
    int cnt = 0;
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (din[i] == 0)
        {
            din[i]--;
            q.push(i);
            topo.push(i);
            cnt++;
        }
    while(q.size())
    {
        int u = q.front();
        q.pop();
        for (int i = h[u]; i != -1; i = ne[i])
        {
            int v = e[i];
            din[v]--;
            if (din[v] == 0)
            {
                q.push(i);
                topo.push(i);
                cnt++;
            }
        }
    }
    return cnt == n;
}

朴素Dijstra

在所有未确定最短路的点中，寻找dist最小的点，用这个点更新所有相邻节点，并确定该点距离已经为最短。

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
int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool vis[N];   // 存储每个点的最短路是否已经确定

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

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

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

        vis[u] = true;
    }

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

堆优化Dijstra

使用堆维护距离与相应的节点。

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
using PII = pair<int,int>;

int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool vis[N];     // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({0, 1});      // first存储距离，second存储节点编号

    while (pq.size())
    {
        int d, u;
        tie(d, u) = pq.top();
        // C++ 17 or above: auto [d, u] = pq.top();
        pq.pop();
        

        if (vis[u] || dist[u] < d)
            continue;
        vis[u] = true;

        for (int i = h[u]; i != -1; i = ne[i])
        {
            int v = e[i];
            if(dist[v] > dist[u] + w[i])
            {
                dist[v] = dist[u] + w[i];
                pq.push({dist[v], v});
            }
        }
    }

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

Bellman-Ford算法

遍历所有边n次，对于每条边{a, b, w}，判断b是否能被a与w更新。

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, 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];
}

spfa 算法

考虑到在BF算法中，只有当一个节点被更新过后才可能用其更新相邻节点，所以记录哪些节点被更新过，并且只从这些节点中取点更新相邻节点。

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 u = q.front();
        q.pop();
        st[u] = false;

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

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

floyd算法

考虑到任何一条路径都可以转化为两条更短的路径，所以通过枚举拆分路径的方式维护最短路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void init()
{
    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;
}

// 算法结束后，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]);
}

朴素版prim算法

从一个点开始扩张生成树。每次选取生成树的相邻节点中最近的节点放在生成树中，最后得到的必定是最小生成树。

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;
}

Kruskal算法

枚举从短到长的所有边，逐个挑选。若选取了某条边后会形成环，则不取这条边，否则取。

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
int n, m;       
int p[N];       

struct Edge
{
    int a, b, w;
} edges[M * 2];

int n, m;
int dist[N];
int p[N];

int find(int x)
{
    if (p[x] == x)
        return x;
    else
        return p[x] = find(p[x]);
}

void add(int a, int b)
{
    p[find(a)] = find(b);
}

int kruskal()
{
    for (int i = 1; i <= n; i++)
        p[i] = i;
    sort(edges + 1, edges + m + 1, [](Edge a, Edge b) -> bool
         { return a.w < b.w; });
    int sum = 0;
    for (int i = 1; i <= m; i++)
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        if (find(a) != find(b))
        {
            add(a, b);
            sum += w;
        }
    }
    return sum;
}

染色法判断二分图

考虑到二分图等价于图中是否存在偶数环，故选取两种颜色，相邻节点染不同的颜色，当出现矛盾时，则不存在偶数环，故不为二分图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int color[N];
bool flag;

bool dfs(int u, int c)
{
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        if (!color[v])
        {
            if (!dfs(v, 3 - c))
                return false;
        }
        else if (color[v] == c)
            return false;
    }
    return true;
}

匈牙利算法求二分图最大匹配

将二分图划分为左右两侧。对于每个左侧节点，逐个考虑是否可以连接右侧节点。若右侧节点不存在连接，则直接连接。若右侧节点存在连接，则检测该连接对应的左侧节点是否可以重新分配右侧节点。需要注意的是，当需要重新分配时，应直接从下一个右侧节点开始检测而非检测所有右侧节点。

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
int n1, n2;
int match[N];
bool st[N];

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

int hungary()
{
    int res = 0;
    for (int i = 1; i <= n1; i++)
    {
        memset(st, 0, sizeof(st));
        if (find(i))
            res++;
    }
    return res;
}

二分图中求最小点覆盖、最大独立集与最大团

可以证明二分图中最小点覆盖等于最大匹配数，所以直接求一遍最大匹配即可。

在二分图中，求最大独立集只需把最小点覆盖去掉即可，故解为 n−mn - m （mm 为最小点覆盖）。否则为NP问题。

最大团与最大独立集为互补关系。

Tarjan算法求强连通分量

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
int timestamp = 0, scc_cnt = 0;
stack<int> stk;
bool in_stk[N];
int dfn[N], low[N], id[N];

void tarjan(int u)
{
    dfn[u] = low[u] = timestamp++;
    stk.push(u), in_stk[u] = true;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        if (!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (in_stk[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u])
    {
        ++scc_cnt;
        do
        {
            v = stk.top();
            stk.pop();
            in_stk[v] = false;
            id[v] = scc_cnt;
        } while (v != u);
    }
}

LCA (倍增 在线)

预处理 fa(i,j)fa(i, j) 表示从节点 ii 开始往上跳 2j2^j 步后可以到达的距离。使用二进制拼凑的方法进行跳跃，先将两点跳到统一深度上，然后再跳到祖先节点之前。

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
int depth[N], fa[N][K + 1];

void bfs(int r)
{
    memset(depth, 0x3f, sizeof(depth));
    depth[0] = 0, depth[r] = 1;
    queue<int> q;
    q.push(r);
    while (q.size())
    {
        int u = q.front();
        q.pop();
        for (int i = h[u]; i != -1; i = ne[i])
        {
            int v = e[i];
            if (depth[v] > depth[u] + 1)
            {
                depth[v] = depth[u] + 1;
                q.push(v);
                fa[v][0] = u;
                for (int k = 1; fa[v][k - 1]; k++)
                    fa[v][k] = fa[fa[v][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a, int b)
{
    if (depth[a] < depth[b])
        swap(a, b);
    for (int k = K; k >= 0; k--)
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    if (a == b)
        return a;
    for (int k = K; k >= 0; k--)
        if (fa[a][k] != fa[b][k])
            a = fa[a][k], b = fa[b][k];
    return fa[a][0];
}

LCA(tarjan 离线)

在一次dfs中，将所有节点分为三类：未遍历，遍历中，遍历结束。在遍历的过程中，若要查找某个遍历结束的节点和遍历中的节点的LCA，只需要在正在遍历的路径上找即可。使用并查集维护遍历结束的节点在遍历中的节点的路径上的父节点。

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
void tarjan(int u)
{
    st[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int v = e[i];
        if (!st[v])
        {
            tarjan(v);
            p[v] = u;
        }
    }

    for (auto p : query[u])
    {
        int v, i;
        tie(v, i) = p;
        if (st[v] == 2)
        {
            int anc = find(v);
            res[i] = dist[v] + dist[u] - 2 * dist[anc];
        }
    }
    st[u] = 2;
}