关于图中的环相关问题

2023-11-19 17:46:34

判断无向图是否有环：

无向图中当顶点的数量和边的数量很大的时候，使用dfs存在大量的递归，会导致栈溢出。使用下面的方法可以有效的避免。

判断无向图中是否存在回路（环）的算法描述

如果存在回路，则必存在一个子图，是一个环路。环路中所有顶点的度>=2。

算法：

第一步：删除所有度<=1的顶点及相关的边，并将另外与这些边相关的其它顶点的度减一。

第二步：将度数变为1的顶点排入队列，并从该队列中取出一个顶点重复步骤一。

如果最后还有未删除顶点，则存在环，否则没有环。

            由于有m条边，n个顶点。如果m>=n，则根据图论知识可直接判断存在环路。

    （证明：如果没有环路，则该图必然是k棵树 k>=1。根据树的性质，边的数目m = n-k。k>=1，所以：m<n）

            如果m<n 则按照上面的算法每删除一个度为0的顶点操作一次（最多n次），或每删除一个度为1的顶点（同时删一条边）操作一次（最多m次）。这两种操作的总数不会超过m+n。由于m<n，所以算法复杂度为O(n)

算法分析

判断有向图是否有环：

拓扑排序，将出队元素存入数组，判断存储数组里的元素是否等于 n 。

求无向图的最小环花费：

floyd算法 O (N3)

给出一张无向图，求一个最小环并输出路径。

说说我的感觉：

包含点 i 和点 j 的最小环，我们可以看成是 i 到 j 之间的最短路和次短路的组合，通过 floyd 可求任意两点之间的最短距离，

那么我们只要找到最短路径外的一条最短路来保证 i 和 j 之间可达即可。在做 floyd 循环的同时，我们以环权值最小（最短路权值+次短路权值=最小环权值）为标准，

一直更新每个点的前驱，也就是记录 i 到 j 的最短路径，以及，能够松弛 i 和 j 的点 k （k 不在 i 到 j 的最短路径中）中代价最小的那个（也就是 i 到 j 之间的次短路），

然后按环的自然顺序输出即可。

    #include<cstdio>
    #include<cstring>
    #define find_min(a,b) a<b?a:b
     
    const int N = 101;
    const int INF = 0x7ffffff;
    int mat[N][N],dist[N][N],pre[N][N],path[N],n;
     
    int main()
    {
        int i,j,k,m,a,b,c;
        int num;
        
        while(~scanf("%d%d",&n,&m)){
            for(i=1;i<=n;i++){
                for(j=1;j<=n;j++){
                    mat[i][j]=dist[i][j]=INF;
                    pre[i][j]=i;
                }
            }
            while(m--){
                scanf("%d%d%d",&a,&b,&c);
                mat[a][b]=mat[b][a]=dist[a][b]=dist[b][a]=find_min(mat[a][b],c);
            }
     
            int min=INF;
            for(k=1;k<=n;k++){//最短路径外一点将最短路首尾链接,那么就得到一个最小环
                for(i=1;i<k;i++){
                    for(j=i+1;j<k;j++){
                        //求最小环不能用两点间最短路松弛,因为(i,k)之间的最短路,(k,j)之间的最短路可能有重合的部分
                        //所以mat[][]其实是不更新的,这里和单纯的floyd最短路不一样
                        //dist[i][j]保存的是 i 到 j 的最短路权值和
                        int tmp=dist[i][j]+mat[i][k]+mat[k][j];//这里 k 分别和 i 还有 j 在mat中直接相连
                        if(tmp<min){
                            min=tmp;
                            num=0;
                            int p=j;
                            while(p!=i){//回溯
                                path[num++]=p;
                                p=pre[i][p];//pre[i][j]表示 i 到 j 最短路径上 j 前面的一个点
                            }
                            path[num++]=i;
                            path[num++]=k;
                        }
                    }
                }
                for(i=1;i<=n;i++){
                    for(j=1;j<=n;j++){
                        if(dist[i][j]>dist[i][k]+dist[k][j]){
                            dist[i][j]=dist[i][k]+dist[k][j];//dist[][]保存两点间最短距离
                            pre[i][j]=pre[k][j];
                        }
                    }
                }
            }
            if(min==INF)puts("No solution.");
            else{
                printf("%d",path[0]);
                for(i=1;i<num;i++)
                    printf(" %d",path[i]);
                puts("");
            }
        }
        return 0;
    }

View Code

Dijkstra算法 O(M*Mlog)

任意一个环的权值，我们都可以看成两个有边相连的结点i、j的直接距离加上i、j间不包含边(边i->j)的最短路径。求最短路径我们第一个想到的就是Dijkstra算法。

而Dijkstra所求的是一个点到所有点的最短距离。

用Dijkstra所求的i、j的最短距离一定是i、j的直接距离(如果i，j连通)，所以我们需要先将i、j的边从图中删除(若i，j不连通，则不用删除)，

再用Dijkstra求新图中i、j的最短距离即可。所以我们每次在图中选取一条边，把它从图中删掉．

然后对删掉的那条边所对应的2点进行Dijkstra，也就是m次Dijkstra

给出题目：http://acm.hdu.edu.cn/showproblem.php?pid=6005

给你m条边，每条边给你两个城市的坐标，还有两个城市道路之间有成本
让你求一个最小成本的周期，至少包含三个城市。

#include <bits/stdc++.h>
 
#define pii pair<int,int>
 
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1e4+15;
const int maxm = 8e3+43;
int t,cnt,m,x,y,w,u,v,p,res,head[maxm];
struct edge{
    int to,nxt,w;
}e[maxm<<1];
struct cmp{
    bool operator()(const pii a,const pii b){
        return a.second > b.second;
    }
};
map<pii,int> vis;
inline void add(int x,int y,int _w){
    e[++cnt].to = y;e[cnt].w = _w;
    e[cnt].nxt = head[x];head[x] = cnt;
}
int dis[maxm];
void init(){
    vis.clear();
    cnt = 0;res = inf;p = 0;
    memset(head,0,sizeof(head));
}
void dijkstra(int x,int y){
    memset(dis,inf,sizeof(dis));
    priority_queue<pii,vector<pii>,cmp> q;
    dis[x] = 0;
    q.push(pii(x,0));
    while(!q.empty()){
        pii now = q.top();q.pop();
        int uu = now.first;         
        if(uu == y || now.second > res) return ;            //剪枝
        if(dis[uu] < now.second) continue;
        for(int i = head[uu];i;i = e[i].nxt){
            int vv = e[i].to;
            if((uu==x&&vv==y)||(uu==y&&vv==x)) continue;  //这条边是删除的边
            if(dis[vv] > dis[uu]+e[i].w){
                dis[vv] = dis[uu] + e[i].w;
                q.push(pii(vv,dis[vv]));
            }
        }
    }
}
int main(){
    scanf("%d",&t);
    for(int Case = 1; Case <= t; ++Case){
        init();
        scanf("%d",&m);
        for(int i = 1;i <= m; ++i){
            scanf("%d %d",&x,&y);
            if(!vis[pii(x,y)]) u = ++p,vis[pii(x,y)] = u;
            else u = vis[pii(x,y)];
            scanf("%d %d %d",&x,&y,&w);
            if(!vis[pii(x,y)]) v = ++p,vis[pii(x,y)] = v;
            else v = vis[pii(x,y)];
            add(u,v,w);
            add(v,u,w);
        }
        for(int i = 1;i <= p; ++i){
            for(int j = head[i]; j ;j = e[j].nxt){
                if(i >= e[j].to) continue;
                dijkstra(i,e[j].to);
                res = min(res,dis[e[j].to]+e[j].w);
            }
        }
        printf("Case #%d: %d\n",Case,res==inf ? 0:res);    
    }
    return 0;
}

View Code

求有向图的最小环花费：

floyd跑最短路，之后对于每个i 比较 dist[ i ][ i ] 的大小即可。

O(n(n+m)log)

码农公寓