深度优先搜索输出有向图中的全部环(JAVA)
深度优先搜索输出有向图中的所有环(JAVA)
如图:求出有向图的所有环。
运行:
C:\java>java TestCycle
Cycle:4 2 5
Cycle:1 3 4 2 5 6 0
Cycle:2 5 6 0
Cycle:2 5 6
源码:
如图:求出有向图的所有环。
import java.util.ArrayList; import java.util.Arrays; public class TestCycle { private int n; private int[] visited;//节点状态,值为0的是未访问的 private int[][] e;//有向图的邻接矩阵 private ArrayList<Integer> trace=new ArrayList<Integer>();//从出发节点到当前节点的轨迹 private boolean hasCycle=false; public TestCycle(int n,int[][] e){ this.n=n; visited=new int[n]; Arrays.fill(visited,0); this.e=e; } 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<n;i++) { if(e[v][i]==1) findCycle(i); } trace.remove(trace.size()-1); } public boolean getHasCycle(){ return hasCycle; } public static void main(String[] args) { int n=7; int[][] e={ {0,1,1,0,0,0,0}, {0,0,0,1,0,0,0}, {0,0,0,0,0,1,0}, {0,0,0,0,1,0,0}, {0,0,1,0,0,0,0}, {0,0,0,0,1,0,1}, {1,0,1,0,0,0,0}};//有向图的邻接矩阵,值大家任意改. TestCycle tc=new TestCycle(n,e); tc.findCycle(1); if(!tc.hasCycle) System.out.println("No Cycle."); } }
运行:
C:\java>java TestCycle
Cycle:4 2 5
Cycle:1 3 4 2 5 6 0
Cycle:2 5 6 0
Cycle:2 5 6
源码: