Я реализую код для обнаружения цикла в неориентированном графе, используя методы поиска/объединения непересекающихся множеств.
Вот реализация:
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
из disjoinset
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