Contoh dalam artikel ini menjelaskan bagaimana Java mengimplementasikan breadth-first traversal (BFS) untuk menghitung jalur terpendek. Bagikan dengan semua orang untuk referensi Anda. Analisis spesifiknya adalah sebagai berikut:
Kami menggunakan string untuk mewakili titik puncak grafik untuk mensimulasikan lokasi Ruang Kelas, Alun-Alun, Toilet, Kantin, Gerbang Selatan, dan Gerbang Utara di sekolah, lalu menghitung jalur terpendek antara dua titik mana pun.
Seperti yang ditunjukkan di bawah ini:
Misalnya, jika saya ingin pergi dari Gerbang Utara ke Kantin, keluaran programnya adalah:
BFS: Dari [Gerbang Utara] ke [Kantin]:Kantin PersegiGerbang Utara
Pertama tentukan algoritma antarmuka Algoritma:
Algoritma antarmuka publik { /** * Jalankan algoritma*/ void perform(Grafik g, String sourceVertex); /** * Dapatkan jalur*/ Peta<String, String> getPath();}Kemudian, tentukan grafiknya:
/** * (Tidak terarah) grafik*/publik kelas Grafik { // Titik awal grafik private String firstVertax; // Daftar kedekatan private Map<String, List<String>> adj = new HashMap<>(); / Algoritma Traversal algoritma Algoritma privat; public Graph(Algoritma algoritma) { this.algorithm = algoritma; } /** * Jalankan algoritma*/ public void selesai() { algoritma.perform(ini, firstVertax); } /** * Dapatkan jalur terpendek dari titik awal ke titik {@code vertex} * @param vertex * @return */ public Stack<String> findPathTo(String vertex) { Stack<String> stack = new Stack< >() ; stack.add(vertex); Peta<String, String> jalur = algoritma.getPath(); untuk (String location = path.get(vertex) ; false == location.equals(firstVertax) ; lokasi = jalur.dapatkan(lokasi)) { tumpukan.push(lokasi } tumpukan.push(firstVertax, String toVertex) { if (firstVertax == null) { firstVertax = fromVertex; } adj.get(fromVertex).add(toVertex); adj.get(toVertex).add(fromVertex); } /** * Tambahkan simpul*/ public void addVertex(String simpul) { adj.put(vertex, new ArrayList<>() } public Map<String, List<String>> getAdj() { return adj; }}Di sini kita menggunakan pola desain strategis untuk memisahkan algoritme dari kelas Graph, dan memilih algoritme traversal untuk Graph dengan meneruskan implementasi antarmuka Algoritma saat membuat objek Graph.
Grafik publik(Algoritma algoritma) { this.algorithm = algoritma }Struktur penyimpanan grafik tidak berarah adalah daftar kedekatan. Di sini, Peta digunakan untuk mewakili daftar kedekatan. Kunci peta adalah lokasi sekolah (String), dan nilainya adalah daftar lokasi (Daftar<String>) terhubung ke lokasi.
// Daftar kedekatan peta pribadi<String, Daftar<String>> adj = new HashMap<>();
Kemudian, tulis implementasi BFS dari antarmuka Algoritma:
/** * Merangkum algoritma BFS*/kelas publik BroadFristSearchAlgorithm mengimplementasikan Algoritma { // Menyimpan lokasi yang dikunjungi private List<String> yang dikunjungiVertex; // Menyimpan jalur terpendek private Map<String, String> path; g, String sourceVertex) { if (null == VisitVertex) { VisitVertex = New ArrayList<>() } if (null == path) { path = new HashMap<>(); } BFS(g, sourceVertex } @Override public Map<String, String> getPath() { jalur kembali; } private void BFS(Grafik g, String sourceVertex) { Antrean<String> antrian = new LinkedList<>(); // Tandai titik awal yang dikunjungiVertex.add(sourceVertex); // Enqueuekan titik awal queue.add(sourceVertex); antrian.isEmpty()) { String ver = antrian.poll(); Daftar<String> toBeVisitedVertex = g.getAdj().get(ver); untuk (String v : toBeVisitedVertex) { if (false == VisitVertex.contains( v)) { mengunjungiVertex.add(v); path.put(v, ver); antrian.add(v);Diantaranya, path adalah tipe Map yang artinya jalur dari nilai ke kunci.
Deskripsi algoritma BFS:
1. Tandai asal sebagai telah dikunjungi dan masukkan ke dalam antrian.
2. Ambil sebuah simpul dari antrian dan sambungkan semua simpul ke simpul tersebut.
3. Lintasi simpul-simpul ini, tentukan terlebih dahulu apakah simpul tersebut telah dikunjungi, jika belum, tandai titik tersebut sebagai telah dikunjungi, catat jalur saat ini, dan enqueuekan simpul saat ini.
4. Ulangi langkah 2 dan 3 hingga antrian kosong.
Kasus uji:
String[] vertex = {"Gerbang Utara", "Gerbang Selatan", "Ruang Kelas", "Kotak", "Toilet", "Tepi Kantin[] edge = { Tepi baru("Gerbang Utara", "Ruang Kelas" ), Tepian baru("Gerbang Utara", "Kotak"), Tepian baru("Ruang Kelas", "Toilet"), Tepian baru("Kotak", "Toilet"), Tepian baru("Kotak", "Kantin"), new Edge("Toilet", "Gerbang Selatan"), new Edge("Toilet", "Gerbang Selatan"), };@Test public void testBFS() { Grafik g = Grafik baru(New BroadFristSearchAlgorithm( )); addVertex(g); addEdge(g); g.selesai(); Stack<String> hasil = g.findPathTo("Kantin"); System.out.println("BFS: Dari [Gerbang Utara] ke [Kantin]:"); while (!result.isEmpty()) { System.out.println(result.pop() } }Saya harap artikel ini bermanfaat untuk pemrograman Java semua orang.