Graf Wajaran dan Aplikasi

Graf ialah graf berwajaran jika setiap tepi diberi pemberat. Graf berwajaran mempunyai banyak aplikasi praktikal.

Rajah di atas menganggap bahawa graf mewakili bilangan penerbangan antara bandar. Anda boleh menggunakan BFS untuk mencari bilangan penerbangan paling sedikit antara dua bandar. Andaikan bahawa tepi mewakili jarak pemanduan antara bandar seperti yang ditunjukkan dalam Rajah di bawah. Bagaimanakah anda mencari jumlah jarak minimum untuk menghubungkan semua bandar? Bagaimanakah anda mencari jalan terpendek antara dua bandar? Bab ini akan menjawab soalan-soalan ini. Yang pertama dikenali sebagai masalah minimum spanning tree (MST) dan yang kedua sebagai masalah laluan terpendek.

Bab sebelumnya memperkenalkan konsep graf. Anda mempelajari cara mewakili tepi menggunakan tatasusunan tepi, senarai tepi, matriks bersebelahan dan senarai bersebelahan serta cara memodelkan graf menggunakan antara muka Graf, kelas Graf Abstrak dan UnweightedGraph kelas. Bab sebelumnya juga memperkenalkan dua teknik penting untuk merentasi graf: carian mendalam-dahulu dan carian luas-dahulu, dan menggunakan traversal untuk menyelesaikan masalah praktikal. Catatan berikut akan memperkenalkan graf berwajaran. Anda akan mempelajari algoritma untuk mencari pepohon rentang minimum dalam pos dan algoritma untuk mencari laluan terpendek dalam pos .

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