当前位置:   article > 正文

「图论」判环、求环、最小环_tarjan判环

tarjan判环

判断是否存在环

  • 无向图

    • 并查集(不仅能判环,还能判奇环,即利用带权并查集)
    • dfs标记法
    • SPFA(给边加权值的方法来通过判正负环进行判环)
    • Tarjan锁点,如果存在双联通分量则存在环
  • 有向图

    • dfs标记法,用fa数组来记录
    • 拓扑排序,跑完拓扑排序后剩下没跑出来的点的度数如果都大于等于2,则说明有环
    • SPFA(给边加权值的方法来通过判正负环进行判环)
    • Tarjan缩点,如果存在双联通分量则存在环
  • 特殊环

    • 奇环:带权并查集、二分图染色法
    • 正负环:spfa、tarjan缩点

找出所有环上的所有点

  • dfs打标记法,用fa数组来记录
  • 跑spfa用fa数组记录
  • tarjan缩点后的双联通分量就是多个环的合并

拓扑排序找出与度数有关的点集->退化到度数为2的环

可以使用类似拓扑排序的方法找到一个点集,使得点集在任意一个点的度都大于等于k。如果k=2,那么就是一个环

以特殊点为源点点最小环

利用spfa即可,我们初始化的时候不要把源点s的值初始化成0,而是inf,然后手动更新一遍与源点相连的点,更新他们的disvis,并把这些点塞到队列里面,然后跑最短路就行,这样最小环就是dis[s]

vector<int>G[MAX];
int fa[MAX];
int dis[MAX];
bool vis[MAX];

int SPFA(int s){
    queue<int>q;
    for(int i = 1; i <= n; ++i)dis[i] = inf;
    mem(vis, 0);
    for(auto v : G[s]){
        vis[v] = 1;
        fa[v] = s;
        q.push(v);
        dis[v] = 1;
    }
    while(!q.empty()){
        int u = q.front();q.pop();
        for(auto v : G[u]){
            if(dis[v] > dis[u] + 1){
                dis[v] = dis[u] + 1;
                fa[v] = u;
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    return dis[s];
}
  • 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

Floyed找最小环

for(int k = 1; k <= n; ++k){
    for(int i = 1; i < k; ++i){
        for(int j = i + 1; j < k; ++j){
            ans = min(ans, tr[i][k] + tr[k][j] + dis[i][j]);//更新最小环
        }
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);//更新最小值
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小丑西瓜9/article/detail/64579
推荐阅读
相关标签
  

闽ICP备14008679号