如何判断一个图中是否存在环路

最近公司的项目中，有个树形结构变图结构的问题。本来我们对项目中实体之间的关系是按树形结构来表示的，也就是说实体之间不会重用，也不会有环。现在我们需要变成图的结构，实体之间可以重用，但不能有环。那么该如何解决这个问题呢？

我们先定义出什么是环：

环定义：从一条边出发，如果能回到当前边则证明有环。

没有环的图

可见，根据定义，上面的图不存在环。因为从任意一条边出发都不可能回到自身。下面给出一个带有环的图。

图三

图中红色箭头的3，4，5构成了一个环路。因为从3、4、5任一点出发，都可以回到起始点。那么我们如何使用代码去判断出图中是否有环呢？

代码逻辑

首先你可能想到的是，判断节点是否被重用过。但是这个办法行不通，第一张图给出的就是这个思路的反例。

正确的办法是，我们需要明确这是用图来描述的结构，图的定义可以参考图数据结构。

例如上面这张图，我们可以给出这个图的所有边（在项目中，每条边就是一个ResRelation）：

1 -> 2

1 -> 3

1 -> 4

2 -> 4

3 -> 4

4 -> 5

5 -> 3

我们需要维持一个集合color来标记某条边是否被访问过，维持一个队列queue用来进行迭代算法。当迭代遍历整个图的时候，首先将1(也可以是任意起始点)加入队列，由于1的可达路径为[2,3,4]。所有我们将1的可达路径加入队列。同时color中标记1 -> 2,1 ->3,1 -> 4。

继续迭代，当前queue中的节点是[2,3,4]，先弹出2，找到了2的可达路径为4，同时将2 -> 4标记为已访问。节点3同样的道理。

这时候queue中的值可能重复，因为[1,2,3]都可达4，代码中我做了一个去重。因此现在queue中只有4。

寻找4的可达路径，我们找到了5，同时标记4 -> 5。根据5寻找可达路径，我们找到了3，同时标记5 -> 3。此时queue中只有一个节点3，再次迭代寻找3的可达路径，我们找到了3 -> 4，这时候我们发现这个边被访问过了。因此这个图中有环。代码如图：

private static boolean isCircle(String id, List resRelationList) {

boolean isCircle = false;

/* 队列*/

LinkedList queue = Lists.newLinkedList(Lists.newArrayList(id));

/* 标记集合*/

Set color=new HashSet<>();

while (queue.size() > 0) {

String parentId = queue.poll();

for (ResRelation i : resRelationList) {

/* 找到节点的对应的关系，也就是边*/

if (parentId.equals(i.getStart_id())) {

/* 查看边是否被访问过*/

if(!color.contains(i)){

color.add(i);

if(!queue.contains(i.getEnd_id())){

/*加入队列 */

queue.add(i.getEnd_id());

}

}else{

/* 如果重复访问，则有环*/

isCircle=true;

queue.clear();

break;

}

}

}

}

return isCircle;

}