近期项目遇到一个检测环的问题，记录一波。
大概的需求，前端用户可以输入n个节点，节点之前为有向线段连接，数据从一个叶子节点（只有输出边线）不断向它的连线指向的节点计算，直到这个图算完，如下图
其中叶子节点（节点1）为起始节点，它不停地向前计算，直到算完算到末端节点（节点4及节点7）
这里产生一个问题，如果用户输入的图是有环的，那这个环内就是个死循环，将产生严重后果，所以不允许用户如何输入，那如何检测这个环呢？
算法一：深度遍历
这个算法是最容易想到的，就是把路径都遍历一遍，当其中一条路径检测到重复的节点时，就说明这条路径进入了死循环。
如上图，从末端节点开始，找出所有的路径
1：找出末端节点 4和7
2：从末端节点开始遍历，比如从4开始
4 -> 2 ok
7 -> 5 -> 3 -> 1 ok
7 -> 5 -> 3 -> 2 -> 6 -> 3... NG 3重复出现说明有环 计算结束
代码实现：
public static List<Long> checkLoopWithTraversal(List<EleLine> lines){
//找出所有终止结点
List<Long> finalIds = getFinalIds(lines);
//整理结点关系图，构建结点对象
Map<Long, Ele> allEleMap = new HashMap<Long, Ele>();
for(EleLine line: lines) {
Ele toEle = allEleMap.get(line.getToEleId());
if (toEle == null) {
toEle = new Ele(line.getToEleId());
allEleMap.put(toEle.getId(), toEle);
}
Ele fromEle = allEleMap.get(line.getFromEleId());
if (fromEle == null) {
fromEle = new Ele(line.getFromEleId());
allEleMap.put(fromEle.getId(), fromEle);
}
toEle.getFromEleList().add(fromEle);
}
for(Long id: finalIds) {
//定义set 存放某一条路径的所有id
Set<Long> pathIds = new HashSet<Long>();
//从终止结点出发遍历
Long resultEleId = checkLoopEle(pathIds, allEleMap.get(id));
if (resultEleId != null) {
//有问问题
return new ArrayList<Long>(pathIds);
}
}
return null;
}
/**
* 嵌套递归调用
* @param pathIds
* @param currentEle
* @return
*/
private static Long checkLoopEle(Set<Long> pathIds, Ele currentEle) {
if (pathIds.contains(currentEle.getId())) {
return currentEle.getId();
}
if (currentEle.getFromEleList().size() == 0) {
//路径到底，无循环
return null;
}
Long result;
pathIds.add(currentEle.getId());
for (Ele ele : currentEle.getFromEleList()) {
result = checkLoopEle(pathIds, ele);
if (result != null) {
return result;
}
}
//该结点下所有子结点检查完毕无循环，将该结点从路径id集合删除
pathIds.remove(currentEle.getId());
return null;
}
算法二：拓扑剥离
假设有100个结点，每为10层，每一次10个结点，相邻的两层的各个结点均与另一层有10个连线，这张图如果把上面的算法去查找，则遍历总张图至少需要遍历10的10次方，这个对cup的占用是可怕的，所以我们研究 另一种法。
如果图里面存在终止结点，那边终止结点肯定不可能在死循环里，所以我们可以把这此终止结点都清除得到新的图，新的图重复上面的动作，最终得到一张没有终止结点的图，或者没有结点的图，前者就是存在死循环，后者就是不存在的。回上文章开头的例子，其循环过程如下：
图：1 2 3 4 5 6 7
图：1 2 3 5 6
图：1 2 3 6
剩下的图没有终止结点了，说明有死循环。
代码实现
private static boolean checkLoopWithTopology(List<EleLine> lines) {
List<EleLine> checkLines = new ArrayList<EleLine>(lines);
do {
int size = checkLines.size();
removeFromOnlyEle(checkLines);
if (size == checkLines.size()) {
return false;
}
} while (checkLines.size() > 0);
return true;
}
/**
* 移除所有的终止结点
* @param checkLines
*/
private static void removeFromOnlyEle(List<EleLine> checkLines) {
Set<Long> fromIds = new HashSet<Long>();
for (EleLine line : checkLines) {
fromIds.add(line.getFromEleId());
}
for (int i=0; i<checkLines.size(); i++) {
EleLine line = checkLines.get(i);
if (!fromIds.contains(line.getFromEleId()) || !fromIds.contains(line.getToEleId())) {
checkLines.remove(i);
i--;
}
}
}再看这个100个结点的例子，用这种算法，只需10次循环就可解出答案。
完整代码参考githup: https://github.com/Kavli/lesson
评论列表