我正在使用不相交集的查找/联合方法实现无向图中的循环检测代码 .
这是实施:
public boolean isCyclicundirected(){
int k;
ArrayDisjointSet set = new ArrayDisjointSet(5);
//Set<Vertex> parents = new HashSet<Vertex>();
System.out.println(vertexMap);
Set<String> allVertices = vertexMap.keySet();
for (String v : allVertices){
Iterator<Edge> e = vertexMap.get(v).adj.iterator();
while (e.hasNext()){
int i = Integer.parseInt(vertexMap.get(v).name);
int j = Integer.parseInt(e.next().target.name);
if (set.isConnected(i, j))
return true;
else
k = set.join(i, j);
System.out.println(set);
}
}
return false;
}
这是分离的 isConnected
public boolean isConnected(int i, int j){
return find(i)==find(j);
}
如果两个节点具有相同的根(由 find
返回),则表示存在循环 . 对于这样没有循环 (1,2),(2,3),(3,4)
的图形,我的方法返回true . 我无法理解什么是错的 .
编辑最新:建议如下:
public boolean isCyclicundirected() {
int k;
HashSet<HashSet<Vertex>> vertexpairs = new HashSet<HashSet<Vertex>>();
ArrayDisjointSet set = new ArrayDisjointSet(100);
Set<String> allVertices = vertexMap.keySet();
for (String v : allVertices) {
Vertex current = vertexMap.get(v);
for (Edge e : current.adj){
Vertex nextVertex = e.target;
HashSet<Vertex> temp = new HashSet<Vertex>();
temp.add(nextVertex);
temp.add(current);
if (!vertexpairs.contains(temp)) {
vertexpairs.add(temp);
int i = Integer.parseInt(current.name);
int j = Integer.parseInt(nextVertex.name);
if (set.isConnected(i, j))
return true;
else
k = set.join(i, j);
System.out.println(set);
}
}
}
return false;
}
我得到 node:java.util.NoSuchElementException
1 回答
您遍历每个边缘两次,每边一次 . 你只需要考虑一次边缘 .