日期:2014-05-20  浏览次数:20665 次

贴一个我写的找出有向图中所有环的算法
最近有需要就在网上找了找求有向图中环的算法,结果发现大多思路都很混乱.
于是乎自己写了下贴出来,大家有兴趣可以看看.
Java code

import java.util.ArrayList;
public class Test7 {
    static private int[] visited={0,0,0,0,0,0,0};//7个节点,0为未访问
    static private int[][] e={
                            {0,1,1,0,0,0,0},
                            {0,0,1,1,0,0,0},
                            {0,0,0,0,0,1,0},
                            {0,0,0,0,1,0,0},
                            {0,0,0,0,0,0,0},
                            {0,0,0,0,0,0,1},
                            {1,0,0,0,0,0,0}};//邻接矩阵,值大家任意改.
    static ArrayList<Integer> trace=new ArrayList<Integer>();//从出发节点到当前节点的轨迹
    static boolean hasCycle=false;
    public static void main(String[] args) {
        findCycle(0);
        if(!hasCycle) 
            System.out.println("No Cycle.");
    }
    static void findCycle(int v)   //递归DFS
    {
        if(visited[v]==1)
        {
            int j;
            if((j=trace.indexOf(v))!=-1)
            {
                hasCycle=true;
                System.out.print("Cycle:");
                while(j<trace.size())
                {
                    System.out.print(trace.get(j)+" ");
                    j++;
                }
                System.out.print("\n");
                return;
            }
            return;
        }
        visited[v]=1;
        trace.add(v);
        
        for(int i=0;i<7;i++)
        {
            if(e[v][i]==1)
                findCycle(i);
        }
        trace.remove(trace.size()-1);
    }
}



------解决方案--------------------
恩,代码写的不错,几个变量为什么都要static呢,只是感觉没必要。。