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

判断是否存在环

• 无向图

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

• 有向图

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

• 特殊环

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

找出所有环上的所有点

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

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

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

以特殊点为源点点最小环

利用spfa即可，我们初始化的时候不要把源点s的值初始化成0，而是inf，然后手动更新一遍与源点相连的点，更新他们的dis和vis，并把这些点塞到队列里面，然后跑最短路就行，这样最小环就是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