java 查找循环依赖
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/6613828/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Find cyclic dependency
提问by Anton K.
Possible Duplicate:
Finding all cycles in graph
可能的重复：
查找图中的所有循环
I have a task I've been wrapping my brain around and still have a trouble inplementing it. Here it goes: There is a class:
我有一项任务，我一直在绞尽脑汁，但仍然无法执行。它是这样的：有一个类：
public class Package {
private String name;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
private List<Package> dependencies;
public List<Package> getDependencies() {
return dependencies;
}
public void setDependencies(List<Package> dependencies) {
this.dependencies = dependencies;
}
public Package(String name){
this.name = name;
this.dependencies = new ArrayList<Package>();
}
//any bunch of methods here))
}
And there is another one:
还有一个：
public class Project {
private String name;
private List<Package> packages = new ArrayList<Package>();
public boolean hasCyclic(){
//**//implementation should be here
}
}
I need to find whether a list of packages in a project has a cyclic dependency or not. For example A->B->C->B - found, return true or A->C->Z->A - found, return true. First thing that comes to mind is to get all packages' names, sort them and find duplicates. But somewhere, deep in my brain, something tells me it is not the most optimal solution. Can you guys help me out here? Thank you so much in advance.
我需要查找项目中的包列表是否具有循环依赖关系。例如 A->B->C->B - 找到，返回真或 A->C->Z->A - 找到，返回真。首先想到的是获取所有包的名称，对它们进行排序并找到重复项。但是在我大脑深处的某个地方，某事告诉我这不是最佳解决方案。你们能帮我吗？非常感谢你提前。
回答by Marcelo
回答by davin
There is a cycle <==> The DFS forest (from any starting point) has a back branch.
有一个循环 <==> DFS 森林（从任何起点）都有一个返回分支。
Linear running time. Simple implementation.
线性运行时间。简单的实现。
回答by matt b
Think of the project's dependencies as a tree, and then simply do a depth-first traversal of the tree, keeping track of the package name when you visit each node. If you encounter a duplicate name before the traversal reaches the furthest level it can, then you have a cyclic dependency.
把项目的依赖想象成一棵树，然后简单地对树进行深度优先遍历，在访问每个节点时跟踪包名称。如果在遍历到达它所能达到的最远级别之前遇到重复的名称，那么您就有了循环依赖。
回答by Johan Sj?berg
There are a number of variants with varying memory/execution time characteristics. Some ideas are
有许多变体具有不同的内存/执行时间特性。一些想法是
- Put all dependencies in a HashMap, detecting cycles means to find find a non-null value in when performing the write check
- Use two "pointers" to traverse the list with one pointer faster than the other.
- Either the pointers will terminate or one will eventually catch up in a cyclic loop such that the element at pointer A is the same as the element in pointer B.
- Provide checks at insertion time. When inserting a new element, traverse the list to see if element to insert is already present or not.
- 将所有的依赖放在一个HashMap中，检测循环意味着在执行写检查时找到一个非空值
- 使用两个“指针”以一个指针比另一个更快地遍历列表。
- 要么指针将终止，要么最终在循环中赶上指针 A 处的元素与指针 B 中的元素相同。
- 在插入时提供检查。插入新元素时，遍历列表以查看要插入的元素是否已经存在。
回答by Anton K.
That's the code I've come up with. Seems to work)
这就是我想出的代码。似乎工作）
package com.mycompany.app;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
public class Package {
private String name;
private List<Package> dependencies;
private List<String> allNames = new ArrayList<String>();
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public List<Package> getDependencies() {
return dependencies;
}
public void setDependencies(List<Package> dependencies) {
this.dependencies = dependencies;
}
public Package(String name){
this.name = name;
this.dependencies = new ArrayList<Package>();
}
public boolean hasPackages(){
return !dependencies.isEmpty();
}
public List<String> getAllNames(){
allNames = new ArrayList<String>();
allNames.add(name);
for (Package pkg : dependencies){
if (pkg.hasPackages()){
allNames.addAll(pkg.getAllNames());
}
else{
allNames.add(pkg.getName());
}
}
return allNames;
}
public Package addPackage(Package pkg){
dependencies.add(pkg);
return this;
}
public boolean hasCyclic(){
List<String> names = getAllNames();
Set<String> visited = new HashSet<String>();
for (String name : names){
if (visited.contains(name)){
return true;
}
else{
visited.add(name);
}
}
return false;
}
}
