Java学习者论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

手机号码,快捷登录

恭喜Java学习者论坛(https://www.javaxxz.com)已经为数万Java学习者服务超过8年了!积累会员资料超过10000G+
成为本站VIP会员,下载本站10000G+会员资源,购买链接:点击进入购买VIP会员
JAVA高级面试进阶视频教程Java架构师系统进阶VIP课程

分布式高可用全栈开发微服务教程

Go语言视频零基础入门到精通

Java架构师3期(课件+源码)

Java开发全终端实战租房项目视频教程

SpringBoot2.X入门到高级使用教程

大数据培训第六期全套视频教程

深度学习(CNN RNN GAN)算法原理

Java亿级流量电商系统视频教程

互联网架构师视频教程

年薪50万Spark2.0从入门到精通

年薪50万!人工智能学习路线教程

年薪50万!大数据从入门到精通学习路线年薪50万!机器学习入门到精通视频教程
仿小米商城类app和小程序视频教程深度学习数据分析基础到实战最新黑马javaEE2.1就业课程从 0到JVM实战高手教程 MySQL入门到精通教程
查看: 1183|回复: 0

[算法学习]判断有向图中有无环的算法

[复制链接]
  • TA的每日心情
    开心
    2021-3-12 23:18
  • 签到天数: 2 天

    [LV.1]初来乍到

    发表于 2014-12-6 00:07:23 | 显示全部楼层 |阅读模式
    求有向图中环的算法
    1. import java.util.ArrayList;
    2. import java.util.Arrays;
    3. public class TestCycle {
    4.      private int n;
    5.      private int[] visited;//节点状态,值为0的是未访问的
    6.      private int[][] e;//邻接矩阵
    7.      private ArrayList< Integer> trace=new ArrayList< Integer>();//从出发节点到当前节点的轨迹
    8.      private boolean hasCycle=false;
    9.      public TestCycle(int n,int[][] e){
    10.          this.n=n;
    11.          visited=new int[n];
    12.          Arrays.fill(visited,0);
    13.          this.e=e;
    14.      }
    15.    
    16.      void findCycle(int v)   //递归DFS
    17.     {
    18.         if(visited[v]==1)
    19.         {
    20.             int j;
    21.             if((j=trace.indexOf(v))!=-1)
    22.             {
    23.                 hasCycle=true;
    24.                 System.out.print("Cycle:");
    25.                 while(j< trace.size())
    26.                 {
    27.                     System.out.print(trace.get(j)+" ");
    28.                     j++;
    29.                 }
    30.                 System.out.print("
    31. ");
    32.                 return;
    33.             }
    34.             return;
    35.         }
    36.         visited[v]=1;
    37.         trace.add(v);
    38.         
    39.         for(int i=0;i< n;i++)
    40.         {
    41.             if(e[v][i]==1)
    42.                 findCycle(i);
    43.         }
    44.         trace.remove(trace.size()-1);
    45.     }
    46.   
    47.   public boolean getHasCycle(){
    48.       return hasCycle;
    49.   }
    50.    public static void main(String[] args) {
    51.         int n=7;
    52.         int[][] e={
    53.                     {0,1,1,0,0,0,0},
    54.                     {0,0,0,1,0,0,0},
    55.                     {0,0,0,0,0,1,0},
    56.                     {0,0,0,0,1,0,0},
    57.                     {0,0,1,0,0,0,0},
    58.                     {0,0,0,0,1,0,1},
    59.                     {1,0,1,0,0,0,0}};//邻接矩阵,值大家任意改.
    60.         TestCycle tc=new TestCycle(n,e);
    61.         tc.findCycle(1);
    62.         if(!tc.hasCycle)
    63.             System.out.println("No Cycle.");
    64.     }
    65. }
    复制代码
    D:java>java TestCycle
    Cycle:4 2 5
    Cycle:1 3 4 2 5 6 0
    Cycle:2 5 6 0
    Cycle:2 5 6

       
         
         
          
          

            
          

            
          
         
       

      


    源码下载:http://file.javaxxz.com/2014/12/6/000723156.zip
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    QQ|手机版|Java学习者论坛 ( 声明:本站资料整理自互联网,用于Java学习者交流学习使用,对资料版权不负任何法律责任,若有侵权请及时联系客服屏蔽删除 )

    GMT+8, 2024-3-28 22:17 , Processed in 0.351713 second(s), 46 queries .

    Powered by Discuz! X3.4

    © 2001-2017 Comsenz Inc.

    快速回复 返回顶部 返回列表