Überprüfen, ob ein Java-Diagramm einen Zyklus hat

1. Übersicht

In diesem kurzen Tutorial erfahren Sie, wie Sie einen Zyklus in einem bestimmten gerichteten Diagramm erkennen können.

2. Graphendarstellung

In diesem Tutorial bleiben wir bei der Darstellung der Adjazenzliste.

Zunächst definieren wir einen Vertex in Java:

public class Vertex { private String label; private boolean beingVisited; private boolean visited; private List adjacencyList; public Vertex(String label) { this.label = label; this.adjacencyList = new ArrayList(); } public void addNeighbor(Vertex adjacent) { this.adjacencyList.add(adjacent); } //getters and setters }

Hier enthält die Adjazenzliste eines Scheitelpunkts v eine Liste aller Scheitelpunkte neben v . Die Methode addNeighbor () fügt der Adjazenzliste von v einen benachbarten Scheitelpunkt hinzu .

Wir haben auch zwei boolesche Parameter definiert : " besucht" und " besucht", die angeben , ob der Knoten gerade besucht wird oder bereits besucht wurde.

Ein Graph kann als eine Gruppe von Eckpunkten oder Knoten betrachtet werden, die durch die Kanten verbunden sind.

Lassen Sie uns nun schnell ein Diagramm in Java darstellen:

public class Graph { private List vertices; public Graph() { this.vertices = new ArrayList(); } public void addVertex(Vertex vertex) { this.vertices.add(vertex); } public void addEdge(Vertex from, Vertex to) { from.addNeighbor(to); } // ... }

Wir werden die Methoden addVertex () und addEdge () verwenden, um neue Scheitelpunkte und Kanten in unser Diagramm einzufügen .

3. Zykluserkennung

Um einen Zyklus in einem gerichteten Diagramm zu erkennen, verwenden wir eine Variation der DFS- Durchquerung:

  • Nehmen Sie einen nicht besuchten Scheitelpunkt v und markieren Sie seinen Status als besucht
  • Überprüfen Sie für jeden benachbarten Scheitelpunkt u von v :
    • Wenn sich u bereits im Status "Besucht" befindet , bedeutet dies eindeutig, dass eine Rückwärtskante vorhanden ist und daher ein Zyklus erkannt wurde
    • Wenn u noch in einem unvisited Zustand ist, werden wir besuchen rekursiv u in einer Tiefe-ersten Art und Weise
  • Aktualisieren Sie den Scheitelpunkt v ‚s beingVisited Flag auf falsch und seine besuchten Flagge zu wahren

Beachten Sie, dass sich alle Scheitelpunkte unseres Diagramms anfangs in einem nicht besuchten Zustand befinden, da sowohl die Flags " Besucht" als auch " Besucht" mit " Falsch" initialisiert werden .

Schauen wir uns nun unsere Java-Lösung an:

public boolean hasCycle(Vertex sourceVertex) { sourceVertex.setBeingVisited(true); for (Vertex neighbor : sourceVertex.getAdjacencyList()) { if (neighbor.isBeingVisited()) { // backward edge exists return true; } else if (!neighbor.isVisited() && hasCycle(neighbor)) { return true; } } sourceVertex.setBeingVisited(false); sourceVertex.setVisited(true); return false; }

Wir können jeden Scheitelpunkt in einem Diagramm als Quelle oder Startscheitelpunkt verwenden.

Für ein nicht verbundenes Diagramm müssen wir eine zusätzliche Wrapper-Methode hinzufügen:

public boolean hasCycle() { for (Vertex vertex : vertices) { if (!vertex.isVisited() && hasCycle(vertex)) { return true; } } return false; }

Dies soll sicherstellen, dass wir jede Komponente eines nicht verbundenen Diagramms besuchen, um einen Zyklus zu erkennen.

4. Implementierungstests

Betrachten wir den folgenden zyklisch gerichteten Graphen:

Wir können schnell eine JUnit schreiben, um unsere hasCycle () -Methode für dieses Diagramm zu überprüfen :

@Test public void givenGraph_whenCycleExists_thenReturnTrue() { Vertex vertexA = new Vertex("A"); Vertex vertexB = new Vertex("B"); Vertex vertexC = new Vertex("C") Vertex vertexD = new Vertex("D"); Graph graph = new Graph(); graph.addVertex(vertexA); graph.addVertex(vertexB); graph.addVertex(vertexC); graph.addVertex(vertexD); graph.addEdge(vertexA, vertexB); graph.addEdge(vertexB, vertexC); graph.addEdge(vertexC, vertexA); graph.addEdge(vertexD, vertexC); assertTrue(graph.hasCycle()); }

Hier hat unsere hasCycle () -Methode true zurückgegeben, was bedeutet, dass unser Graph zyklisch ist.

5. Schlussfolgerung

In diesem Tutorial haben wir gelernt, wie Sie überprüfen, ob in einem bestimmten gerichteten Diagramm in Java ein Zyklus vorhanden ist.

Wie üblich ist die Code-Implementierung mit Beispielen auf Github verfügbar.