最近项目中需要研究了一下有向图的环路问题。一个IT企业中有成千上万个应用，各个应用之间都是相互依赖的，一个用户请求进来后，会调用一系列应用，比如A调B、B调C、C调D等。这样所有的应用形成一个有向图，那么如果这个有向图中出现了环路，就悲剧了，用户的请求如果进入这个环路，那么他永远也得不到响应。所以就有需要去判断这个应用组成的有向图中是否含有环路，如果有就要打印出所有的环路(打印的时候按照从小到大的顺序打印)
上面就是我前几天在阿里做的一道代码题，半小时，不是原题但是原理一样，很悲催自己什么都没有写出来，自己春招准备的少，还没有时间回顾之前的数据结构，拿道题的时候根本没有往数据结构那几个方面上去想，过后才想到这不就是在一个图里面找环路，采用广度优先遍历的算法，加上排序(我这里采用快速排序算法)实现，实现代码如下(阿里的编程题，需要将输入转成二维数组，这里就不转了，直接就是二维数组)，这里代码如下
import java.util.Stack;
public class Main{
static Stack trace=new Stack();
static boolean hasCycle=false;
static final int POINT_NUM=9;
static int[][] edge={
{0,0,0,0,0,0,0,0,1},
{0,0,0,1,1,0,0,0,0},
{1,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,1,0},
{0,0,0,0,0,0,0,1,0},
{0,1,0,0,0,0,0,0,0},
{1,0,0,0,0,0,0,0,0},
{0,0,1,0,0,0,1,0,0},
{0,0,0,0,0,1,0,0,0}} ;
public static void main(String[] args){
}
public static void findcle(int point){
int j=0;
if((j=trace.indexOf(point))!=-1)
{
hasCycle=true;
int[] data=new int[trace.size()-j];
int i=0;
while(j<trace.size()){
data[i]=trace.get(j);
i++;
j++;
}
quickSort(data,0,data.length-1);
for(int m=0;m<data.length;m++)
System.out.print(data[m]+" ");
System.out.print("\n");
}
trace.push(point);
for(int i=0;i<POINT_NUM;i++)
if(edge[point][i]==1)
findcle(i);
trace.pop();
}
public static void quickSort(int[] data,int left,int right){
if(left<right){
int value=data[left];
int i=left;
int j=right;
while(i<j){
while(i<j && data[j]>=value)j--;
data[i]=data[j];
while(i<j && data[i]<=value)i++;
data[j]=data[i];
}
data[i]=value;
quickSort(data,left,i-1);
quickSort(data,i+1,right);
}
}
}
</pre>
总结一下方法： 主要用到的是广度优先遍历和快速排序
广度优先遍历：就是从头节点开始向下遍历，每路过一个节点就把它标记为已访问，一层一层访问过去。
深度优先遍历：从头节点开始，直接向下访问，访问不了，才跳回上一层访问
快排：选一个基本点，把数组分成两半，左边比他小，右边比他大，然后一直循环下去分，知道分到一个的时候就已经排好序了
归并排序：先分，合起来的时候再排序，和快排相反。
要是在当时写出来多好。。。。。
