Verifica se un grafico Java ha un ciclo

1. Panoramica

In questo rapido tutorial, impareremo come rilevare un ciclo in un dato grafico diretto.

2. Rappresentazione grafica

Per questo tutorial, ci atterremo alla rappresentazione del grafico dell'elenco di adiacenza.

Innanzitutto, iniziamo definendo un vertice 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 }

Qui, l' adiacenzaList di un vertice v contiene un elenco di tutti i vertici adiacenti a v . Il metodo addNerowse () aggiunge un vertice adiacente all'elenco delle adiacenze di v .

Abbiamo anche definito due parametri booleani , beingVisited e visitati, che rappresentano se il nodo è attualmente visitato o è già stato visitato.

Un grafo può essere pensato come un gruppo di vertici o nodi collegati attraverso i bordi.

Quindi, rappresentiamo ora rapidamente un grafico in Java:

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); } // ... }

Useremo i metodi addVertex () e addEdge () per aggiungere nuovi vertici e bordi nel nostro grafico.

3. Rilevamento del ciclo

Per rilevare un ciclo in un grafico diretto, useremo una variazione dell'attraversamento DFS :

  • Raccogli un vertice non visitato v e contrassegna il suo stato come Visitato
  • Per ogni vertice adiacente u di v, controlla:
    • Se u è già nello stato beingVisited , significa chiaramente che esiste un bordo all'indietro e quindi è stato rilevato un ciclo
    • Se u è ancora in uno stato di non visitato, faremo in modo ricorsivo visita u in un modo in profondità
  • Aggiornare il vertice v 's beingVisited bandiera per falso e la sua visitato bandiera vera

Nota che tutti i vertici del nostro grafo sono inizialmente in uno stato non visitato poiché sia ​​il flag beingVisited che quello visitati sono inizializzati con false .

Diamo ora un'occhiata alla nostra soluzione Java:

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; }

Possiamo usare qualsiasi vertice in un grafo come sorgente o vertice iniziale.

Per un grafico disconnesso, dovremo aggiungere un metodo wrapper aggiuntivo:

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

Questo per garantire che visitiamo ogni componente di un grafico disconnesso per rilevare un ciclo.

4. Test di implementazione

Consideriamo il seguente grafico ciclico diretto:

Possiamo scrivere rapidamente una JUnit per verificare il nostro metodo hasCycle () per questo grafico:

@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()); }

Qui, il nostro metodo hasCycle () ha restituito true denotando che il nostro grafico è ciclico.

5. conclusione

In questo tutorial, abbiamo imparato come verificare se esiste un ciclo in un dato grafo diretto in Java.

Come al solito, l'implementazione del codice con esempi è disponibile su Github.