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

javalearner

求有向图中环的算法

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