`
128kj
  • 浏览: 600300 次
  • 来自: ...
社区版块
存档分类
最新评论

如何求无向图的最小环

    博客分类:
阅读更多
POJ1734
题意:给定一个N个点的无向图,求一个最小环(各边权值和最小的环)并输出路径。


样例:
Sample Input

5 7   (图有五个点,七条边)
1 4 1  (顶点1与4之间有一条边,权值为1,以下同)
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20

Sample Output

1 3 5 2



思路:朴素的求法是:枚举每一条边(假设为e(i,j)),删除它,再求(i,j)之间的最短距离(用Dijkstra算法),该环就是dis(i,j) + e(i,j)。这样就需要依次枚举每条边,然后求一次最短路,时间复杂度为:O(N*N*M), 在N和M的数据规模较大时就会超时。

有一种改进的算法, 就是在求两点之间的最短路的时候,顺便求出最小环,即Floyd求最小环法。代码为:

void Floyd(){  
    for(int k=1;k<=N;k++){//环中的最大结点编号   
        for(int i=1;i<k;i++){//依次枚举k两端的结点 i , j   
            for(int j=i+1;j<k;j++){  
                ans = MIN(ans, dis[i][j] + G[i][k] + G[k][j]);//最大节点为k的环的最短路径
            }  
        }  
        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]);  
            }  
        }  
    }  
 }  


该算法的证明:

   一个环中的最大结点为K(编号最大),与其相连的两个点为i,j ,这个环的最短长度为: G[i][k] + G[k][j ] + i到j的路径中所有结点编号都不大于k的最短路径长度,根据floyd的原理,在最外层循环做一个k-1次之后, dis[i][j] 则代表了i到j的路径中所有结点的编号都不大于k的最短路径。

本题的代码:
import java.util.Scanner;
public class Main{
 static final int INF = 0x3f3f3f3f ;  
 private int n;  //顶点数
 private int[][] maze;  //邻接矩阵
 private int[][] dis;  //dis[][]保存可以达到的最短距离,会变化; 
 private int[][] fa;  //标记(i,j)最短路径上,距离j最近的那个结点   
 private int[] res;//保存最小环的路径
 private int temp;

  public Main(int n,int[][] fa,int[][] maze){
     this.n=n;
     this.fa=fa;
     this.maze=maze;
     dis=new int[n+1][n+1];
     res=new int[n+1];
     
  }
  

 private void solve(int i, int j ,int k){//记录最小环的路径    
    temp = 0 ;  
    while(j != i){  
        res[temp++] = j  ;  
        j = fa[i][j] ;  
    }  
    res[temp++] = i ;  
    res[temp++] = k ;  
}  

 private void Floyd(){  //Floyd求任意两点i,j之间的最短距离dis[i][j]
    for(int i=1;i<=n;i++){  
        for(int j=1;j<=n;j++){  
            dis[i][j] = maze[i][j] ;  
        }  
    }  
    int ans = INF ;  
    for(int k=1;k<=n;k++){  
        for(int i=1;i<k;i++){  
            for(int j=i+1;j<k;j++){  
                if(dis[i][j]<INF && maze[i][k]<INF && maze[k][j]<INF && ans>dis[i][j] + maze[i][k] + maze[k][j]){  
                    ans = dis[i][j] + maze[i][k] + maze[k][j] ; //最大节点为k的环的最短路径
                    solve(i,j,k); //记录环的各顶点 
                }  
            }  
        }  
        for(int i=1;i<=n;i++){  
            for(int j=1;j<=n;j++){  
                if(dis[i][k]<INF && dis[k][j]<INF && dis[i][j]>dis[i][k] + dis[k][j]){  
                    dis[i][j] = dis[i][k] + dis[k][j] ;  
                    fa[i][j] = fa[k][j] ;  
                    fa[j][i] = fa[k][i] ;  
                }  
            }  
        }     
    }  
    if(ans == INF){  
        System.out.printf("No solution.\n");  
    }  
    else{  
        for(int i=0;i<temp;i++){  
            System.out.printf("%d%c",res[i],i==temp-1?'\n':' ');  
        }  
    }  
} 
 public static void  main(String args[]){  
    Scanner in=new Scanner(System.in);
    int a ,b ,c ;  
    while(in.hasNext()){  
       int n=in.nextInt();//顶点数
       int m=in.nextInt();//边数
       int maze[][]=new int[n+1][m+1];
       int fa[][]=new int[n+1][n+1];
        for(int i=1;i<=n;i++){  //初始化图
            for(int j=1;j<=m;j++){  
                if(i == j)  maze[i][j] = 0;   
                else        maze[i][j] = INF ;  
            }  
        }  
        for(int i=1;i<=m;i++){  
           a=in.nextInt();//边的一端
           b=in.nextInt();//边的另一端
           c=in.nextInt();//边的权
           if(maze[a][b] > c){  //重边取权小的
                maze[a][b] = maze[b][a] = c ;  
                fa[a][b] = a ; //标记(i,j)最短路径上,距离j最近的那个结点    
                fa[b][a] = b ;    
            }     
        }  
       Main ma=new Main(n,fa,maze);
        ma.Floyd() ;  
    }     
 }
}  

源码:
  • 大小: 951 Bytes
分享到:
评论

相关推荐

    aaa.rar_无向图 环_无向图所有环_无向图最小环_最小生成树_树所有操作

    判断图中是否存在环,无向图5分,有向图10分 给出顶点u和v,判断u到v是否存在路径(5分) 10、求顶点u到v的一条简单路径(10分) 11、求顶点u到v的所有简单路径(15分) 12、求顶点u到v的最短路径(10分) 13、求...

    图论中的圈与块,无向图的最小环

    割边则是在无向图中,如果删除这条边,会导致原本连通的两个顶点变为不连通。这两种概念常用于分析图的结构稳定性,特别是在网络设计和容错系统中。 2. **最小生成树**(MST):MST是无向加权图中边的子集,它包含...

    邻接表实现无向图的建立与遍历,最小生成树以及最短路径

    最小生成树是无权图或加权无向图中一棵边的子集,它连接了图中的所有顶点,且边的权重之和尽可能小。Prim算法是一种贪心算法,从一个顶点开始,逐步添加边到当前生成树,每次选择与已生成树连接且权值最小的边。...

    数据结构的无向图的连通分量

    ### 数据结构中的无向图与连通分量 #### 一、无向图与连通性的定义 ...通过以上介绍,我们可以了解到无向图的连通分量、生成树及其构建方法、最小生成树等相关概念和技术,在解决实际问题时具有重要的作用。

    无向图连通图的最小生成树 数据结构

    最小生成树(Minimum Spanning Tree, MST)是无向图的一个经典概念,它在图论和网络优化问题中广泛应用。 最小生成树问题旨在找到一个无环的边子集,这些边连接了图中的所有节点,并且这些边的总权重最小。这在设计...

    无向图的广度优先生成树

    无向图的广度优先生成树(BFS Tree)是一种在无向图中寻找特定根节点的树形结构,该树的构造方式是通过广度优先搜索(Breadth-First Search, BFS)进行的。在图论和计算机科学中,这种遍历方法常用于寻找最短路径、...

    tt.rar_M?n_无向图环_无向连通图 最小生成树_连通图

    请输出无向连通图最小生成树权重之和。 输入: 第一行是2个整数,分别表示顶点个数n和边数m。接下来的m行中,每一行第一个整数表示边的开始顶点,第二个表示边的结束顶点,第三个表示这条边的权重。 ( 测试数据中保证...

    用Prim算法求无向图的最小生成树 (2).pdf

    最小生成树是指一个无环且连通的子图,它包含原图的所有顶点,并且边的权重之和尽可能小。在Prim算法中,我们逐步构建这个子图,每次添加一条连接已选顶点和未选顶点的最小权重边。 在给定的代码中,首先定义了最大...

    数据结构用C语言写的无向图的算法

    综上所述,用C语言实现无向图的算法时,需要掌握图的逻辑结构、存储结构(邻接矩阵和邻接表)、遍历算法(DFS和BFS)、最小生成树算法、最短路径算法以及拓扑排序等核心知识。在实际编程中,根据图的特性选择合适的...

    图的着色遍历有向无环图判断

    **定义:** 有向无环图(Directed Acyclic Graph, DAG)是一种特殊的有向图,其中没有任何一条路径能够形成一个环路。换句话说,在一个DAG中,不存在任何起点和终点相同的有向路径。 **应用场景:** - **任务调度**...

    数据结构作业之六图图

    3. 最小生成树:Prim算法或Kruskal算法用于寻找带权重的无向图中的最小生成树,即连接所有顶点且边权重和最小的子集。 此外,图还有其他高级概念,如强连通分量(有向图中任何两个顶点都可以互相到达的子图)、二分...

    无向图的各项功能的课程设计

    14. **最小生成树**:找到一个加权无向图的边子集,构成一棵树,且所有顶点都被包含,总权重最小。Kruskal's或Prim's算法可以实现。 15. **关键路径**:在有向加权网络中,从源点到汇点的最长路径,用于项目管理。...

    Prim算法与Kruskal算法求最小生成树

    最小生成树是图论中的一个重要概念,用于寻找一个无向加权图的边集合,使得这些边连接了图中的所有顶点,同时整个边集合的总权重尽可能小。在这个问题中,Prim算法和Kruskal算法是两种常用的方法。 1. Prim算法: ...

    图论- 环与块- 最小环.rar

    环是指在无向图或有向图中,由若干个顶点构成的一条路径,这条路径的起始顶点与结束顶点相同,形成一个闭合的链。例如,如果我们有一个由四个顶点A、B、C和D组成的无向图,其中存在边AB、BC、CD和DA,那么这四个顶点...

    深度优先算法(DFS)遍历有向无环图寻找最优路径

    总结来说,深度优先搜索在有向无环图中寻找最优路径是一种有效的方法,它通过遍历所有可能的路径并实时更新最优解,最终找到具有最小权值的路径。在实现过程中,需要注意优化存储结构和搜索过程,以提高效率和准确性...

    无向连通图最小生成树

    请输出无向连通图最小生成树权重之和。 输入 第一行是2个整数,分别表示顶点个数n和边数m。接下来的m行中,每一行第一个整数表示边的开始顶点,第二个表示边的结束顶点,第三个表示这条边的权重。 ( 测试数据中保证图...

    邮递员算法 无向图形式

    在无向图的形式下,这个问题可以被抽象为:给定一个无环连通图,寻找一条通过每条边恰好一次的最短闭合路径。这个问题是NP完全问题,意味着没有已知的多项式时间算法能解决所有实例。 邮递员算法是一种尝试解决邮递...

    数据结构(图)试题及答案

    - **普里姆算法**:适用于加权无向图,从一个顶点开始逐步加入边,保证每次添加的边不形成环且增加的树的总权重最小。 - **克鲁斯卡尔算法**:也适用于加权无向图,按照边的权重从小到大选择边,确保在选择过程中...

    第七章 图作业及答案(50分).docx

    1. 邻接矩阵对称性:无向图的邻接矩阵是对称的,因为无向图的边没有方向,所以矩阵中对应位置的两个元素相等。因此,答案是B。 2. 关键活动时间:在边表示活动的AOE(Activity On Edge)网中,关键活动的最迟开始...

Global site tag (gtag.js) - Google Analytics