图论 – 常用算法模板
|
224
|
0
|
🎓 理工

图的存储

邻接矩阵

int g[N][N];

链式前向星

// 头插邻接表
N 为点数， M 为点数
int h[N], e[M], w[M], ne[M], idx;
void add(int a, int b, int c) { // 插入一条从 a 指向 b 的边，权值为 c
  e[idx] = b;
  w[idx] = c;
  ne[idx] = h[a];
  h[a] = idx ++;
}
int main() {
  memset(h, -1 , sizeof h);
}

存储边

struct edge {
  int a, b, c; // a 指向 b 的权值为 c 的边
  bool operator < (const& e) const { // 这里重新定义该结构体 小于号（<）排序时从小到大
    return c < e.c;
  }
}edges[N];

最短路

朴素 dijkstra 算法

 时间复杂是 O($n^{2}$ + m), n 表示点数，m 表示边数

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

堆优化版 dijkstra 算法

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

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

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

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        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 + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }

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

Bellman-Ford算法

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

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 算法（队列优化的Bellman-Ford算法）

 时间复杂度 平均情况下 O(m)，最坏情况下 O(nm), n 表示点数，m 表示边数
 判断是否有负环时只要统计到达 某个点 的 其它点数 是否大于总点数即可；

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

floyd算法

 时间复杂度是 O($n^{3}$), n 表示点数

初始化：
    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]);
}

连通分量

tarjan 算法（有向图强连通分量）

int h[N], e[M], ne[M], idx;
int dfn[N], low[N], ts; // dfn 记录时间戳， low 记录能到的最小时间戳 
int stk[N], top; //   
int ins[N];
int id[N], cnt;
void tarjan(int u) {
    dfn[u] = low[u] = ++ ts;
    stk[++ top] = u, ins[u] = 1;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (ins[j]) {
            low[u] = min(low[u], dfn[j]);
        }
    }
    if (dfn[u] == low[u]) {
        int y;
        ++ cnt;
        do {
            y = stk[top --];
            ins[y] = 0;
            id[y] = cnt;
        } while (y != u);
    }
}

无向图双连通分量

边的双连通分量

 概括：极大的不包含 桥 的连通块

桥  
 o-o 桥o-o
 | | ↓ | |
 o-o - o-o 
如何找桥？ x
            /
           y
x和y之间是桥 <=> dfn[x] < low[y] y无论如何往上走不到 x 且 low[y] = dfn[y] 即 y 是该连通块最高点

int h[N], e[M], ne[M], idx;
int dfn[N], low[N], ts; // dfn 记录时间戳， low 记录能到的最小时间戳 
int stk[N], top;    
int ins[N];
int id[N], cnt;
int is_bridge[M];
void tarjan(int u, int from) {
    dfn[u] = low[u] = ++ ts;
    stk[++ top] = u;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j, i);
            low[u] = min(low[u], low[j]);
            if (dfn[u] < low[j]) {
                is_bridge[i] = is_bridge[i ^ 1] = true;
            }
        }
        else if (i != (from ^ 1)) {
            low[u] = min(low[u], dfn[j]);
        }
    }
    if (dfn[u] == low[u]) {
        ++ cnt;
        int y;
        do (
            y = stk[top --];
            id[y] = cnt;
        )
        while (y != u);
    }
}

点的双连通分量

 概括：不含 割点 的最大连通块

    割点 
 o-o   o-o
 |  \↓/  |
 o-o-o-o-o 

     z
     |    
     x   
     |
     y

x 是割点：
  low[y] <= dfn[x]
  x 是根节点 或 x 不是根节点，但有至少两个子节点

int h[N], e[M], ne[M], idx;
int dfn[N], low[N], ts; // dfn 记录时间戳， low 记录能到的最小时间戳 
int stk[N], top;    
int ins[N];
int id[N], cnt;
int is_cut[N];
void tarjan(int u) {
    dfn[u] = low[u] = ++ ts;
    int cnt = 0;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
            if (low[j] >= dfn[u]) {
                is_cut[u] = 1; 
            }
        }
    }
}

最小生成树

无向图

朴素版prim算法

 时间复杂度是 O($n^{2}$ + m), n 表示点数，m 表示边数

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算法

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

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

有向图

朱刘算法

int dnf[N], low[N], ts;
int stk[N], ins[N], top;
int id[N], cnt;
int d[N][N], bd[N][N]; // d 存储两个点的距离，d[a][b] 为 a 到 b 的距离，bd 为备份数组 
void tarjan(int u) {
    dfn[u] = low[u] = ++ ts;
    stk[++ top] = u, ins[u] = 1;
    int j = pre[u];
    if (!dfn[j]) {
        tarjan(j);
        low[u] = min(low[u], low[j]);
    }else if (ins[j]) low[u] = min(low[u], dfn[j]);
    if (low[u] == dfn[u]) {
        int y;
        ++ cnt;
        do {
            y = stk[top --];
            ins[y] = 0;
            id[y] = cnt;
        }while (y != u);
    }

} 
int zhuliu() {
    int ret = 0;    
    while (true) {
        // 记录每个点最小入边 
        for (int i = 1; i <= n; ++ i) {
            pre[i] = i;
            for (int j = 1; j <= n; ++ j) {
                if (d[pre][i] > d[j][i]) pre[i] = j; 
            }
        }
        // 判断是否有环 
        memset(dfn, 0, sizeof dfn)l
        ts = cnt = 0;
        for (int i = 1; i <= n; ++ i) {
            if (!dfn[i]) tarjan(i);
        }
        if (cnt == n) {
            for (int i = 2; i <= n; ++ i) ret += d[pre[i][i]];
            break;
        } 

        // 缩点
        for (int i = 1; i <= cnt; ++ i) {
            for (int j = 1; j <= cnt; ++ j) {
                bd[i][j] = INF;
            }
        } 

        for (int i = 1; i <= n; ++ i) {
            for (int j = 1; j <= n; ++ j) {
                if (d[i][j] < INF && id[i] != id[j]) {
                    int a = id[i], b = id[j];
                    if (id[pre[j]] == id[j]) bd[a][b] = min(bd[a][b], d[i][j] - d[pre[j]][j]);
                    else bd[a][b] = min(bd[a][b], d[i][j]);
                }
            }
        }
        n = cnt;
        memcpy(d, bd, sizeof bd);

    }
    return ret;

}

最近公共祖先

倍增算法

int q[N], depth[N], fa[N][M];
void bfs() {
    int hh = 0, tt = -1;
    q[++ tt] = 1;
    depth[1] = 1;
    while (hh <= tt) {
        int t = q[hh ++];
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (!depth[j]) {
                depth[j] = depth[t] + 1;
                fa[j][0] = t;
                for (int k = 1; k <= M; ++ k) {
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
                }
                q[++ tt] = j;
            }
        }

    }   
}
int lca(int x, int y) {
    if (depth[x] < depth[y]) swap(x, y);
    for (int i = M; i >= 0; -- i) {
        if (depth[fa[x][i]] >= depth[y]) {
            x = fa[x][i];
        }
    }
    if (x == y) return x;
    for (int i = M; i >= 0; -- i) {
        if (fa[x][i] != fa[y][i]) {
            x = fa[x][i], y = fa[y][i];
        }
    }
    return fa[x][0];
}

欧拉路径 和 欧拉回路

 欧拉路径存在充分必要条件：
   有向图：起点出度比入度大 1，终点入度比出度大 1，其余点出入度相同 或 所有的点的出入度相同
   无向图：度数为奇数的点只能有 0 个或 2 个

Hierholzer算法

int g[N][N];
int ans[1100], cnt;
// 起点开始，每遍历完一条边，立刻删除
void Hierholzer(int u)
{
    for (int i = 1; i <= n; i ++ )
        if (g[u][i])
        {
            g[u][i] --, g[i][u] -- ; // 此为无向图
            dfs(i);
        }
    ans[ ++ cnt] = u;
}

 欧拉回路存在条件：
   有向图：所有点出入度相同
   无向图：所有点的度数都为偶数

int h[N], e[M], ne[M], idx;
int type, n, m;
int seq[M], cnt; // seq 记录欧拉回路 
void dfs(int u) {
    for (int i = h[u]; i != -1; i = h[u]) {
        if (st[i]) {
            h[u] = ne[i];
            continue;
        }
        // type 为 1 时为无向图， type 为 2 时为有向图 
        if (type == 1) st[i ^ 1] = 1; // 标记反向边 
        int t;
        if (type == 1) {
            t = i / 2;
            if (i & 1) t = -t; 
        } 
        else t = i;
        h[u] = ne[i];
        dfs(e[i]);
        seq[cnt ++] = t;
    }
}

网络流

Edmonds-Karp 算法

 时间复杂度 O(n$m^{2}$) n 表示点数， m 表示边数

int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], pre[N]; // d 记录流量， pre 记录来边
int n, m, S, T;// 
bool st[N];

bool bfs()
{
    int hh = 0, tt = 0;
    memset(st, false, sizeof st);
    q[0] = S, st[S] = true, d[S] = INF;
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if (!st[ver] && f[i])
            {
                st[ver] = true;
                d[ver] = min(d[t], f[i]);
                pre[ver] = i;
                if (ver == T) return true;
                q[ ++ tt] = ver;
            }
        }
    }
    return false;
}

int EK()
{
    int r = 0;
    while (bfs())
    {
        r += d[T];
        for (int i = T; i != S; i = e[pre[i] ^ 1])
            f[pre[i]] -= d[T], f[pre[i] ^ 1] += d[T];
    }
    return r;
}

 费用流

int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N]; // d 记录权值， pre 记录来边， incf 记录到某地最大流量
bool st[N];
int S, T, n, m;
void add(int a, int b, int c, int d) {
    e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx ++;
    e[idx] = a, f[idx] = 0, w[idx] = - d, ne[idx] = h[b], h[b] = idx ++;
}
bool spfa()
{
    int hh = 0, tt = 1;
    memset(d, 0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    q[0] = S, d[S] = 0, incf[S] = INF;
    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if (f[i] && d[ver] > d[t] + w[i])
            {
                d[ver] = d[t] + w[i];
                pre[ver] = i;
                incf[ver] = min(f[i], incf[t]);
                if (!st[ver])
                {
                    q[tt ++ ] = ver;
                    if (tt == N) tt = 0;
                    st[ver] = true;
                }
            }
        }
    }

    return incf[T] > 0;
}

void EK(int& flow, int& cost)
{
    flow = cost = 0;
    while (spfa())
    {
        int t = incf[T];
        flow += t, cost += t * d[T];
        for (int i = T; i != S; i = e[pre[i] ^ 1])
        {
            f[pre[i]] -= t;
            f[pre[i] ^ 1] += t;
        }
    }
}

Dinic算法

int h[N], e[M], ne[M], f[M], idx;
int q[M], cur[N], d[N]; // cur 当前弧优化
int n, m, S, T;
void add(int a, int b, int c){
    e[idx] = b;
    ne[idx] = h[a];
    f[idx] = c;
    h[a] = idx ++;
}

bool bfs() {
    forn(i, 0, N) d[i] = -1;
    int hh = 0, tt = 0;
    q[tt ++] = S;
    d[S] = 0;
    cur[S] = h[S];
    while (hh < tt) {
        int t = q[hh ++];
        for (int i = h[t]; i != -1; i = ne[i]) {
            int ver = e[i];
            if (d[ver] == -1 && f[i]) {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if (ver == T) return true;
                q[tt ++] = ver;
            }
        }
    }
    return false;
}

int find(int u, int limit) {
    if (u == T) return limit;
    int flow = 0;

    for (int i = cur[u]; i != -1 && flow < limit; i = ne[i]) {
        int ver = e[i];
        cur[u] = i;
        if (d[ver] == d[u] + 1 && f[i]) {
            int t = find(ver, min(f[i], limit - flow));
            if (!t) d[ver] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }

    }
    return flow;
}

int dinic() {
    int r = 0, flow = 0;
    while (bfs()) while (flow = find(S, INF)) r += flow;
    return r;
}

prufer 编码

 概括：对于一个 无根树，每次取出最小的一个节点，将其父节点输出，该节点删除；

int d[N], f[N], p[N]; // d 记录度数， f 记录父节点，p 记录 prufer 对应码
int n, m;
void tree2prufer() { // 树 转 prufer 编码
    for (int i = 1; i < n; ++ i) {
        cin >> f[i];
        d[f[i]] ++;
    }

    for (int i = 0, j = 1; i < n - 2;) {
        while (d[j]) ++ j;
        p[i ++] = f[j ++];
        while (i < n - 2 && -- d[p[i - 1]] == 0 && p[i - 1] < j) p[i ++ ] = f[p[i - 1]];
    }
    for (int i = 0; i < n - 2; ++ i) {
        cout << p[i] << " ";
    }
    cout << endl;
}
void prufer2tree() { prufer 编码转 树
    for (int i = 1; i < n - 1; ++ i) {
        cin >> p[i];
        d[p[i]] ++;
    }
    p[n - 1] = n;
    for (int i = 1, j = 1; i < n; ++ i) {
        while (d[j]) ++ j;
        f[j ++] = p[i];
        while (i < n - 1 && -- d[p[i]] == 0 && p[i] < j) f[p[i]] = p[i + 1], ++ i;
    }
    for (int i = 1; i < n; ++ i) {
        cout << f[i] << " ";
    }
    cout << endl;
}

哈夫曼编码

 概括：对于一堆节点，每次取出权值最小的两个节点，组成子节点，其共父节点权值为该两节点权值之和

拓扑序

 概括：从入度为 0 的点开始广搜

图论算法模板
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
															
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

															
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
前缀和与差分

							
							

							
快速排序模板

							
							

							
洛谷GESP C++上机题

							
							

							
YS-GPT

							
							

							
洛谷官方题单【算法1】

							
							

							
洛谷官方题单【入门】

							
							

							
数位DP

							
							

							
蓝桥杯-特殊时间

							
							

							
The 2022 ICPC Asia Xian/Jinan Regional Contest\2022 ICPC 亚洲区域赛西安站和济南站题解记录

							
							

							
数学知识-常用算法模板