Funktioniert dieser DFS -Ansatz zum Erkennen von Zyklen in einem gerichteten Diagramm korrekt oder gibt es versteckte Pr ⇐ Java

[Anonymous]

Ich versuche, Zyklen in einem gerichteten Diagramm mit einem DFS-basierten Ansatz in Java zu erkennen. Ich habe eine Lösung implementiert, die ein besuchter [] -Array verwendet und die Karte aus der Liste der Eingabedandel erstellt. Es scheint in allen von mir geschriebenen Testfällen korrekt zu funktionieren - selbst für getrennte Grafiken und Grafiken mit mehreren Zweigen. Ich möchte sicher sein, dass meine Logik solide ist und wenn es einen Fehler gibt, würde ich es gerne besser verstehen. < /P>
public static boolean hasCycle(List edges, int v) {
boolean[] visited = new boolean[v];
Map map = new HashMap();

for (List list : edges) {
int parent = list.get(0);
List l = map.getOrDefault(parent, new ArrayList());
l.add(list.get(1));
map.put(parent, l);
}

for (int i = 0; i < v; i++) {
if (!visited && dfs(map, visited, i)) {
return true;
}
}

return false;
}

private static boolean dfs(Map map, boolean[] visited, int currentNode) {
if (visited[currentNode]) {
return true;
}

visited[currentNode] = true;

if (map.containsKey(currentNode)) {
for (Integer node : map.get(currentNode)) {
if (dfs(map, visited, node)) {
return true;
}
}
}

return false;
}
< /code>
Beispiel -Testfall < /p>
// Test Case 1 (should return true)
int v1 = 4;
List edges1 = Arrays.asList(
Arrays.asList(0, 1),
Arrays.asList(0, 2),
Arrays.asList(1, 2),
Arrays.asList(2, 0),
Arrays.asList(2, 3)
);
System.out.println("Case 1: " + hasCycle(edges1, v1)); // true

// Test Case 2 (should return false)
int v2 = 4;
List edges2 = Arrays.asList(
Arrays.asList(0, 1),
Arrays.asList(0, 2),
Arrays.asList(1, 2),
Arrays.asList(2, 3)
);
System.out.println("Case 2: " + hasCycle(edges2, v2)); // false

int v3 = 5;
List edges3 = List.of(
List.of(0, 1),
List.of(1, 2),
List.of(2, 0), // Cycle 1: 0 → 1 → 2 → 0
List.of(2, 3),
List.of(3, 4),
List.of(4, 2) // Cycle 2: 2 → 3 → 4 → 2
);

System.out.println("Case 2: " + hasCycle(edges3, v3)); // true

int v4 = 4;
List edges4 = Arrays.asList(
Arrays.asList(0, 1),
Arrays.asList(1, 2),
Arrays.asList(2, 3)
);
System.out.println("Case 4: " + hasCycle(edges4, v4)); // false

int v5 = 6;
List edges5 = Arrays.asList(
Arrays.asList(0, 1),
Arrays.asList(1, 2),
Arrays.asList(3, 4),
Arrays.asList(4, 5),
Arrays.asList(5, 3)
);
System.out.println("Case 5: " + hasCycle(edges5, v5)); // true

int v6 = 3;
List edges6 = Arrays.asList(
Arrays.asList(0, 1),
Arrays.asList(1, 2),
Arrays.asList(0, 2)
);
System.out.println("Case 6: " + hasCycle(edges6, v6)); // false

int v7 = 4;
// Graph: 0 → 1, 0 → 2, 1 → 3, 2 → 3 — no cycle
List edges7 = Arrays.asList(
Arrays.asList(0, 1),
Arrays.asList(0, 2),
Arrays.asList(1, 3),
Arrays.asList(2, 3)
);
System.out.println("Case 7 (no cycle, should be false): " + hasCycle(edges7, v7)); // false
< /code>
Ich habe den Code selbst geschrieben und verschiedene Testfälle manuell erstellt - einschließlich Diagramme mit Zyklen, ohne Zyklen, getrennte Graphen und Diagramme mit mehreren Pfaden zum selben Knoten. In allen Fällen stimmte die Ausgabe mit meinen Erwartungen überein. Ich habe erwartet, dass es Zyklen richtig erfasst, aber jetzt möchte ich mit der Community bestätigen - ist diese Methode für gerichtete Grafiken wirklich zuverlässig? Wenn nicht, kann jemand ein Gegenbeispiel bereitstellen?