streamalism.org

1. Oversikt

I denne raske opplæringen lærer vi hvordan vi kan oppdage en syklus i en gitt rettet graf.

2. Grafrepresentasjon

For denne opplæringen vil vi holde oss til tilgrenselistens grafrepresentasjon.

For det første, la oss starte med å definere en Vertex i Java:

offentlig klasse Vertex {private String label; privat boolsk vesen Besøkt; privat boolsk besøk; private List adjacencyList; public Vertex (String label) {this.label = label; this.adjacencyList = ny ArrayList (); } offentlig tomrom addNeighbor (Vertex tilstøtende) {this.adjacencyList.add (tilstøtende); } // getters og setters}

Her, den nærhetsliste av et toppunkt v har en liste over alle hjørner ved siden av v. De addNeighbor () metoden legger til et nærliggende toppunkt til nærhetslisten til v.

Vi har også definert to boolsk parametere,blir besøkt og besøkt, som representerer om noden for øyeblikket blir besøkt eller allerede har blitt besøkt.

En graf kan betraktes som en gruppe hjørner eller noder som er koblet gjennom kantene.

Så, la oss nå raskt representere en Kurve i Java:

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

Vi bruker addVertex () og addEdge () metoder for å legge til nye hjørner og kanter i grafen vår.

3. Syklusdeteksjon

For å oppdage en syklus i en rettet graf, vi bruker en variant av DFS traversal:

• Plukk opp et ubesøkt toppunkt v og merk tilstanden som blir besøkt
• For hvert nærliggende toppunkt u av v, Sjekk:
  • Hvis u er allerede i blir besøkt tilstand, betyr det helt klart det eksisterer en bakoverkant, og så har en syklus blitt oppdaget
  • Hvis u er ennå i en ubesøkt tilstand, besøker vi rekursivt u på en dybde-første måte
• Oppdater toppunktet v‘S blir besøkt flagg til falsk og dets besøkt flagg til ekte

Noter det alle hjørnene i grafen vår er i utgangspunktet i en ubesøkt tilstand som begge sine blir besøkt og besøkt flagg initialiseres med falsk.

La oss nå se på Java-løsningen vår:

offentlig boolsk hasCycle (Vertex sourceVertex) {sourceVertex.setBeingVisited (true); for (Vertex-nabo: sourceVertex.getAdjacencyList ()) {if (neighbour.isBeingVisited ()) {// bakoverkant eksisterer return true; } annet hvis (! nabo.isVisited () && hasCycle (nabo)) {return true; }} sourceVertex.setBeingVisited (false); sourceVertex.setVisited (true); returner falsk; }

Vi kan bruke hvilket som helst toppunkt i en graf for å være kilden eller startpunktet.

For en frakoblet graf må vi legge til en ekstra innpakningsmetode:

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

Dette er for å sikre at vi besøker alle komponenter i en frakoblet graf for å oppdage en syklus.

4. Implementeringstesting

La oss se på nedenstående syklistriktede graf:

Vi kan raskt skrive en JUnit for å bekrefte vår hasCycle () metode for denne grafen:

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

Her, vår hasCycle () metoden returnert ekte som indikerer at grafen vår er syklisk.

5. Konklusjon

I denne opplæringen lærte vi hvordan vi kan sjekke om det finnes en syklus i en gitt rettet graf i Java.

Som vanlig er kodeimplementeringen med eksempler tilgjengelig på Github.