Memeriksa apakah Grafik Java memiliki Siklus

1. Ikhtisar

Dalam tutorial singkat ini, kita akan belajar bagaimana kita dapat mendeteksi siklus dalam grafik terarah yang diberikan.

2. Representasi Grafik

Untuk tutorial ini, kami akan tetap menggunakan representasi grafik daftar kedekatan.

Pertama, mari kita mulai dengan mendefinisikan Vertex di 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 }

Di sini, adjacencyList dari sebuah simpul v menyimpan daftar dari semua simpul yang berdekatan dengan v . Metode addNe Neighbor () menambahkan simpul tetangga ke daftar adjacency dari v .

Kami juga telah mendefinisikan dua parameter boolean , sedangVisited dan mengunjungi, yang mewakili apakah node sedang dikunjungi atau sudah dikunjungi.

Grafik dapat dianggap sebagai sekelompok simpul atau simpul yang terhubung melalui tepinya.

Jadi, sekarang mari kita dengan cepat merepresentasikan Grafik di 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); } // ... }

Kita akan menggunakan metode addVertex () dan addEdge () untuk menambahkan simpul dan tepi baru dalam grafik kita.

3. Deteksi Siklus

Untuk mendeteksi siklus dalam grafik terarah, kami akan menggunakan variasi traversal DFS :

  • Ambil simpul v yang belum dikunjungi dan tandai statusnya sebagai sedang Dikunjungi
  • Untuk setiap simpul tetangga u dari v, periksa:
    • Jika u sudah dalam status beingVisited , itu jelas berarti ada tepi belakang dan siklus telah terdeteksi
    • Jika u belum dalam keadaan belum dikunjungi, kami akan rekursif mengunjungi u dengan cara depth-first
  • Update vertex v 's beingVisited bendera untuk palsu dan yang mengunjungi bendera untuk benar

Perhatikan bahwa semua simpul dari grafik kami awalnya dalam keadaan tidak dikunjungi karena baik bendera sedangVisited dan dikunjungi mereka diinisialisasi dengan salah .

Sekarang mari kita lihat solusi Java kami:

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

Kita bisa menggunakan simpul manapun dalam grafik untuk menjadi sumber atau simpul awal.

Untuk grafik terputus, kita harus menambahkan metode pembungkus tambahan:

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

Ini untuk memastikan bahwa kami mengunjungi setiap komponen grafik terputus untuk mendeteksi siklus.

4. Pengujian Implementasi

Mari pertimbangkan grafik berarah siklik di bawah ini:

Kami dapat dengan cepat menulis JUnit untuk memverifikasi metode hasCycle () kami untuk grafik ini:

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

Di sini, metode hasCycle () kami mengembalikan nilai true yang menunjukkan bahwa grafik kami bersiklus.

5. Kesimpulan

Dalam tutorial ini, kita belajar bagaimana memeriksa apakah sebuah siklus ada dalam grafik terarah yang diberikan di Java.

Seperti biasa, implementasi kode dengan contoh tersedia di Github.