Laluan Graf

Depth-first dan breadth-first ialah dua cara biasa untuk melintasi graf.
Graf traversalialah proses melawati setiap bucu dalam graf tepat sekali. Terdapat dua cara popular untuk melintasi graf:perjalanan mendalam-pertama(ataupencarian pertama-dalam) danperjalanan lebar-pertama(ataucarian pertama-luas). Kedua-dua traversal menghasilkan pokok spanning, yang boleh dimodelkan menggunakan kelas, seperti yang ditunjukkan dalam Rajah di bawah. Ambil perhatian bahawaTreeialah kelas dalaman yang ditakrifkan dalam kelasGraf Abstrak.AbstractGraph.Treeberbeza daripada antara mukaTreeyang ditakrifkan dalam Mencari Elemen.AbstractGraph.Treeialah kelas khusus yang direka untuk menerangkan perhubungan ibu bapa-anak nod, manakala antara mukaTreementakrifkan operasi biasa seperti mencari, memasukkan dan memadam dalam pokok. Memandangkan tidak perlu melakukan operasi ini untuk pokok rentang,Grafik Abstrak.Pokoktidak ditakrifkan sebagai subjenisPokok.

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

KelasTreementakrifkan tujuh kaedah. KaedahgetRoot()mengembalikan akar pokok. Anda boleh mendapatkan susunan bucu yang dicari dengan menggunakan kaedahgetSearchOrder(). Anda boleh memanggilgetParent(v)untuk mencari induk bucuvdalam carian. MenyebutgetNumberOfVerticesFound()mengembalikan bilangan bucu yang dicari. KaedahgetPath(index)mengembalikan senarai bucu daripada indeks bucu yang ditentukan kepada punca. MenyebutprintPath(v)memaparkan laluan dari akar kev. Anda boleh memaparkan semua tepi dalam pokok menggunakan kaedahprintTree().

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