streamalism.org

1. Oversigt

I denne hurtige vejledning lærer vi, hvordan vi kan registrere en cyklus i en given rettet graf.

2. Grafrepræsentation

I denne tutorial holder vi os til grafrepræsentationen for adjacency list.

Lad os først starte med at definere en Hvirvel i Java:

offentlig klasse Vertex {privat strengemærke; privat boolsk væsen Besøgt; privat boolsk besøgte; privat liste adjacencyList; public Vertex (String label) {this.label = label; this.adjacencyList = ny ArrayList (); } public void addNeighbor (Vertex tilstødende) {this.adjacencyList.add (tilstødende); } // getters og setters}

Her, den nærhedsliste af et toppunkt v har en liste over alle hjørner ved siden af v. Det addNeighbor () metoden tilføjer et nærliggende toppunkt til nærhedslisten over v.

Vi har også defineret to boolsk parametre,bliver besøgt og besøgte, som repræsenterer om noden i øjeblikket er besøgt eller allerede er blevet besøgt.

En graf kan betragtes som en gruppe af hjørner eller noder, der er forbundet gennem kanterne.

Så lad os nu hurtigt repræsentere en Kurve i Java:

offentlig klasse Graf {private List-vertices; offentlig graf () {this.vertices = ny ArrayList (); } public void addVertex (Vertex vertex) {this.vertices.add (vertex); } public void addEdge (Vertex fra, Vertex til) {from.addNeighbor (til); } // ...}

Vi bruger addVertex () og addEdge () metoder til at tilføje nye hjørner og kanter i vores graf.

3. Cyklusregistrering

For at registrere en cyklus i en rettet graf, vi bruger en variation af DFS gennemkørsel:

• Saml et ubesøgt toppunkt v og marker dens tilstand som bliver besøgt
• For hvert nærliggende toppunkt u af v, kontrollere:
  • Hvis u er allerede i bliver besøgt tilstand betyder det klart der findes en bagudkant, og så er en cyklus blevet detekteret
  • Hvis u er endnu i en ubesøgt tilstand, besøger vi rekursivt u på en dybde-første måde
• Opdater toppunktet v'S bliver besøgt flag til falsk ogdet er besøgte flag til rigtigt

Noter det alle hjørnerne i vores graf er oprindeligt i en ubesøgt tilstand som begge deres bliver besøgt og besøgte flag initialiseres med falsk.

Lad os nu se på vores Java-løsning:

public boolean hasCycle (Vertex sourceVertex) {sourceVertex.setBeingVisited (true); for (Vertex-nabo: sourceVertex.getAdjacencyList ()) {hvis (neighbour.isBeingVisited ()) {// bagudkant eksisterer return true; } ellers hvis (! nabo.isVisited () && hasCycle (nabo)) {returner sand; }} sourceVertex.setBeingVisited (false); sourceVertex.setVisited (true); returner falsk; }

Vi kan bruge ethvert toppunkt i en graf til at være kilden eller startpunktet.

For en afbrudt graf skal vi tilføje en ekstra indpakningsmetode:

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

Dette er for at sikre, at vi besøger alle komponenter i en frakoblet graf for at detektere en cyklus.

4. Implementeringstest

Lad os overveje nedenstående cyklisk rettet graf:

Vi kan hurtigt skrive en JUnit for at bekræfte vores hasCycle () metode til denne graf:

@ Test offentlig ugyldighed givenGraph_whenCycleExists_thenReturnTrue () {Vertex vertexA = ny Vertex ("A"); Vertex vertexB = ny Vertex ("B"); Vertex vertexC = ny Vertex ("C") Vertex vertexD = ny Vertex ("D"); Grafgraf = ny graf (); 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 ()); }

Her, vores hasCycle () metoden returneres rigtigt angiver, at vores graf er cyklisk.

5. Konklusion

I denne vejledning lærte vi at kontrollere, om der findes en cyklus i en given rettet graf i Java.

Som normalt er kodeimplementeringen med eksempler tilgængelig på Github.