Artikel ini menjelaskan metode implementasi algoritma breadth-first traversal berbasis Java untuk grafik dalam bentuk contoh. Metode spesifiknya adalah sebagai berikut:
Gunakan matriks ketetanggaan untuk menyimpan metode grafik:
1. Tentukan jumlah simpul dan sisi suatu graf
2. Informasi simpul masukan disimpan dalam simpul array satu dimensi
3. Inisialisasi matriks ketetanggaan;
4. Masukkan setiap sisi secara bergantian dan simpan dalam busur matriks ketetanggaan.
Masukkan nomor urut i dan j dari dua simpul yang menempel pada tepi;
Tetapkan nilai elemen baris ke-i dan kolom ke-j matriks ketetanggaan menjadi 1;
Tetapkan nilai elemen baris ke-j dan kolom ke-i matriks ketetanggaan menjadi 1;
Implementasi traversal luas-pertama:
1. Inisialisasi antrian Q
2. Kunjungi simpul v; dikunjungi[v]=1; simpul v ditambahkan ke antrian Q;
3.sementara (antrian Q tidak kosong)
v=Elemen kepala antrian Q di-dequeued;
w = titik sudut pertama yang berdekatan v
sementara (w ada)
Jika w belum dikunjungi, simpul kunjungan w; dikunjungi[w]=1; simpul w dimasukkan ke dalam antrian Q
w=titik sudut berikutnya yang berdekatan v
Kode implementasinya adalah sebagai berikut:
paket com.teradata.lsw.sort;import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Queue;public class BFS {//Informasi simpul penyimpanan Objek pribadi[] simpul;//Array informasi tepi penyimpanan private int[][] arcs;//Jumlah tepi private int vexnum;// Catat apakah node ke-i telah dikunjungi private boolean[] Visited;//Buat daftar tertaut sementara untuk menyimpan node yang telah dilalui private List<Object> temp = new ArrayList<Object>();/*** @param args* * @author TD_LSW*/public static void main(String[] args) {// TODO Metode yang dibuat secara otomatis stubBFS g = new BFS(8);Character[] vertices = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };g.addVertex(simpul);g.addEdge(0, 1);g .addEdge(0, 2);g.addEdge(1, 3);g.addEdge(1, 4);g.addEdge(3, 5);g.addEdge(4, 5);g.addEdge(2, 6);g.addEdge(2, 7);System.out.println("Traversal lebar-pertama grafik:");g.bfs();}//Lebar- implementasi traversal pertama private void bfs() {// TODO Metode yang dibuat secara otomatis stubfor (int i = 0; i < vexnum; i++) {visited[i] = false;}Antrian<Integer> q = new LinkedList<Integer>();for (int i = 0; i < vexnum; i++) {if (!visited[i]) {visited[i] = true;visit(i );q.add(i); while (!q.isEmpty()) {int j = (Bilangan Bulat) q.remove().intValue();//Menilai bahwa jika semua traversal selesai, tidak perlu mengulang if (temp.size() == vexnum) {q.removeAll(q);return;}for ( int k = ini .firstAdjVex(j); k >= 0; k = ini.nextAdjVex(j, k)) {jika (!mengunjungi[k]) {q.add(k);visited[k] = true;visit(k);}}}}}}// Cari node berikutnya public int firstAdjVex(int i) {for (int j = 0; j < angka vex; j++) {if (arcs[i][j] > 0)kembalikan j;}kembalikan -1;}publik int berikutnyaAdjVex(int i, int k) {untuk (int j = k + 1; j < vexnum; j++) {if (arcs[i][j] > 0)return j;}return -1;}//Inisialisasi tepi grafik private void addEdge(int i, int j) {/ / TODO Metode yang dibuat secara otomatis stubif (i == j)return;arcs[i][j] = 1;arcs[j][i] = 1;}// Inisialisasi node grafik private void addVertex(Object[] object) {// TODO Metode yang dihasilkan secara otomatis stubthis.vertices = objek;}// Inisialisasi grafik public BFS(int n) {// TODO Konstruktor yang dibuat secara otomatis stubvexnum = n ;simpul = Objek baru[n];arcs = int baru[n][n];dikunjungi = boolean[n] baru;for (int i = 0; i < vexnum; i++) {for (int j = 0; j < vexnum; j++) {arcs[i][j] = 0;}}}kunjungan batal pribadi(int i) {// TODO Metode stubtemp yang dibuat secara otomatis .add(simpul[i]);System.out.print(simpul[i] + " ");}}