Laluan Graf

Depth-first dan breadth-first ialah dua cara biasa untuk melintasi graf.
Perjalanan graf ialah proses melawati setiap bucu dalam graf tepat sekali. Terdapat dua cara popular untuk melintasi graf: perjalanan mendalam-pertama (atau carian pertama-dalam) dan perjalanan pertama-dalam (atau keluasan -carian pertama). Kedua-dua traversal menghasilkan pokok spanning, yang boleh dimodelkan menggunakan kelas, seperti yang ditunjukkan dalam Rajah di bawah. Ambil perhatian bahawa Pokok ialah kelas dalaman yang ditakrifkan dalam kelas Graf Abstrak. AbstractGraph.Tree berbeza daripada antara muka Tree yang ditakrifkan dalam Mencari Elemen. AbstractGraph.Tree ialah kelas khusus yang direka untuk menerangkan perhubungan ibu bapa-anak nod, manakala antara muka Tree mentakrifkan operasi biasa seperti mencari, memasukkan dan memadam dalam pokok. Memandangkan tidak perlu melakukan operasi ini untuk pokok rentang, AbstractGraph.Tree tidak ditakrifkan sebagai subjenis Pokok.

Kelas Tree ditakrifkan sebagai kelas dalaman dalam kelas AbstractGraph dalam baris 226–293 dalam AbstractGraph.java. Pembina mencipta pokok dengan akar, tepi dan susunan carian.

Kelas Pokok mentakrifkan tujuh kaedah. Kaedah getRoot() mengembalikan akar pokok. Anda boleh mendapatkan susunan bucu yang dicari dengan menggunakan kaedah getSearchOrder(). Anda boleh memanggil getParent(v) untuk mencari induk bucu v dalam carian. Menyebut getNumberOfVerticesFound() mengembalikan bilangan bucu yang dicari. Kaedah getPath(index) mengembalikan senarai bucu daripada indeks bucu yang ditentukan kepada punca. Menyebut printPath(v) memaparkan laluan dari akar ke v. Anda boleh memaparkan semua tepi dalam pokok menggunakan kaedah printTree().

Atas ialah kandungan terperinci Laluan Graf. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!