Definisi diagram
Grafik terdiri dari set simpul yang tidak kosong dan satu set tepi antara simpul. Biasanya direpresentasikan sebagai: g (v, e), di mana g mewakili grafik, v adalah himpunan simpul dalam grafik g, dan e adalah himpunan tepi dalam grafik G.
Grafik terarah
Tepi terarah: Jika tepi dari simpul VI ke VJ memiliki arah, tepi ini disebut tepi terarah, yang juga menjadi busur (busur). Itu diwakili oleh yang dipesan <vi, vj>. VI disebut ekor busur dan VJ disebut kepala busur.
Diagram yang tidak teratur
Tepi tidak terarah: Jika tepi antara simpul VI ke VJ tidak memiliki arah, tepi ini disebut tepi (tepi) yang tidak diarahkan, dan diwakili oleh pasangan yang tidak berurutan (VI, VJ).
Gambar sederhana
Diagram Sederhana: Dalam struktur grafik, jika tidak ada simpul ke ujungnya sendiri dan tepi yang sama tidak berulang kali, gambar ini disebut diagram sederhana.
Kelas gambar
Menunjukkan simpul
Langkah pertama dalam membuat kelas grafik adalah membuat kelas Vertex untuk menyimpan simpul dan tepi. Kelas ini berfungsi sama dengan kelas simpul daftar tertaut dan pohon pencarian biner. Kelas Vertex memiliki dua anggota data: satu untuk mengidentifikasi simpul dan yang lain untuk menunjukkan apakah telah diakses. Mereka diberi nama label dan dikunjungi masing -masing.
Salinan kode adalah sebagai berikut:
fungsi vertex (label) {
this.label = label;
}
Kami menyimpan semua simpul dalam array, dan di kelas grafik, kami dapat merujuknya dengan posisi mereka di array
Menunjukkan tepi
Informasi aktual grafik disimpan di "tepi" karena mereka menggambarkan struktur grafik. Node induk dari pohon biner hanya dapat memiliki dua node anak, tetapi struktur grafik jauh lebih fleksibel. Sebuah titik dapat memiliki satu tepi atau beberapa tepi yang terhubung ke sana.
Kami akan menggunakan metode mewakili tepi grafik untuk menjadi tabel yang berdekatan atau array tabel yang berdekatan. Itu akan menyimpan array yang terdiri dari daftar simpul simpul yang berdekatan
Bangun grafik
Tentukan kelas grafik berikut:
Salinan kode adalah sebagai berikut:
grafik fungsi (v) {
this.verttices = v; // simpul ke titik tinggi
this.edges = 0;
this.adj = [];
untuk (var i = 0; i <this.verttices; ++ i) {
this.adj [i] = [];
this.adj [i] .push ('');
}
this.addedge = ditambahkan;
this.toString = tostring;
}
Kelas ini mencatat berapa banyak tepi grafik yang diwakili dan menggunakan panjang dan jumlah simpul grafik untuk merekam jumlah simpul.
Salinan kode adalah sebagai berikut:
fungsi ditambahkan () {
this.adj [v] .push (w);
this.adj [w] .push (v);
this.edges ++;
}
Di sini kami menggunakan loop untuk menambahkan subarray untuk setiap elemen dalam array untuk menyimpan semua simpul yang berdekatan dan menginisialisasi semua elemen ke dalam string kosong.
Traversal gambar
Prioritas mendalam Traversal
DepthFirstSearch, juga dikenal sebagai DepthFirstSearch, disebut sebagai DFS singkatnya.
Misalnya, mencari kunci di ruangan, tidak peduli ruangan mana yang Anda mulai, Anda dapat mencari sudut -sudut ruangan, nightstands, meja samping tempat tidur, di bawah tempat tidur, lemari pakaian, lemari TV, dll. Satu per satu, agar tidak melewatkan titik buta. Setelah mencari semua laci dan lemari penyimpanan, lalu mencari kamar sebelah.
Pencarian Prioritas Kedalaman:
Pencarian kedalaman-pertama berarti mengakses simpul yang belum dikunjungi, menandainya sebagaimana diakses, dan kemudian secara rekursif mengakses simpul lain yang belum dikunjungi dalam tabel kedekatan dari simpul awal.
Tambahkan array ke kelas grafik:
Salinan kode adalah sebagai berikut:
this.marked = []; // simpan simpul yang dikunjungi
untuk (var i = 0; i <this.verttices; ++ i) {
this.marked [i] = false; // inisialisasi ke false
}
Fungsi pencarian pertama yang kedalaman:
Salinan kode adalah sebagai berikut:
fungsi dfs (v) {
this.marked [v] = true;
// jika pernyataan tidak diperlukan di sini
if (this.adj [v]! = tidak terdefinisi) {
print ("Visited vertex:" + v);
untuk masing -masing (var w di this.adj [v]) {
if (! this.marked [w]) {
this.dfs (w);
}
}
}
}
Pencarian pertama yang luas
Pencarian lebar-pertama (BFS) adalah metode pencarian buta, dengan tujuan memperluas secara sistematis dan memeriksa semua node dalam grafik untuk menemukan hasil. Dengan kata lain, tidak memperhitungkan lokasi hasil yang mungkin, dan mencari seluruh gambar secara menyeluruh sampai hasilnya ditemukan.
Pencarian pertama yang pertama dimulai dengan simpul pertama, dan cobalah untuk mengakses simpul sedekat mungkin, seperti yang ditunjukkan pada gambar berikut:
Prinsip kerjanya adalah:
1. Pertama temukan simpul yang tidak terjangkau yang berdekatan dengan simpul saat ini dan tambahkan ke daftar dan antrian simpul yang dikunjungi;
2. Kemudian keluarkan Vertex V berikutnya dari grafik dan tambahkan ke daftar simpul yang dikunjungi
3. Akhirnya tambahkan semua simpul yang tidak dikunjungi yang berdekatan dengan V ke antrian
Berikut ini adalah definisi fungsi pencarian pertama yang luas:
Salinan kode adalah sebagai berikut:
fungsi bfs (s) {
var antrian = [];
this.marked = true;
antrian.push (s); // Tambahkan ke ujung antrian
while (queue.length> 0) {
var v = queue.shift (); // hapus dari pemimpin tim
if (v == tidak terdefinisi) {
print ("Visited vertex:" + v);
}
untuk masing -masing (var w di this.adj [v]) {
if (! this.marked [w]) {
this.edgeto [w] = v;
this.marked [w] = true;
antrian.push (w);
}
}
}
}
Jalan terpendek
Saat melakukan pencarian pertama yang luas, jalur terpendek dari satu titik ke titik lain yang terhubung ditemukan secara otomatis
Tentukan jalurnya
Untuk menemukan jalur terpendek, kita perlu memodifikasi algoritma pencarian pertama untuk merekam jalur dari satu titik ke titik lainnya. Kami membutuhkan array untuk menyimpan semua tepi titik berikutnya dari satu titik. Kami menyebutkan edgeto array ini
Salinan kode adalah sebagai berikut:
this.edgeto = []; // Tambahkan baris ini ke kelas grafik
// fungsi BFS
fungsi bfs (s) {
var antrian = [];
this.marked = true;
antrian.push (s); // Tambahkan ke ujung antrian
while (queue.length> 0) {
var v = queue.shift (); // hapus dari pemimpin tim
if (v == tidak terdefinisi) {
print ("Visited vertex:" + v);
}
untuk masing -masing (var w di this.adj [v]) {
if (! this.marked [w]) {
this.edgeto [w] = v;
this.marked [w] = true;
antrian.push (w);
}
}
}
}
Algoritma penyortiran topologi
Penyortiran topologi mengurutkan semua simpul grafik yang diarahkan, sehingga titik tepi terarah dari titik depan ke titik belakang.
Algoritma penyortiran topologi mirip dengan BFS. Perbedaannya adalah bahwa algoritma penyortiran topologi tidak segera mengeluarkan simpul yang diakses, tetapi sebaliknya mengakses semua simpul yang berdekatan dalam tabel yang berdekatan dengan simpul saat ini. Sampai daftar ini habis, simpul saat ini tidak akan didorong ke tumpukan.
Algoritma penyortiran topologi dibagi menjadi dua fungsi. Fungsi pertama adalah topsort (), yang digunakan untuk mengatur proses penyortiran dan memanggil fungsi helper topsorthelper (), dan kemudian menampilkan daftar vertex yang diurutkan.
Pekerjaan utama algoritma penyortiran topologi dilakukan dalam fungsi rekursif Topsorthelper (), yang menandai simpul saat ini yang diakses, dan kemudian secara rekursif mengakses setiap simpul dalam tabel kedekatan verteks saat ini, menandai simpul -simpul ini sebagaimana diakses. Akhirnya, dorong simpul saat ini ke tumpukan.
Salinan kode adalah sebagai berikut:
// fungsi topsort ()
fungsi topsort () {
var stack = [];
var dikunjungi = [];
untuk (var i = 0; i <this.verttices; i ++) {
mengunjungi [i] = false;
}
untuk (var i = 0; i <this.verttices; i ++) {
if (dikunjungi [i] == false) {
this.topsorthelper (i, mengunjungi, menumpuk);
}
}
untuk (var i = 0; i <stack.length; i ++) {
if (stack [i]! = Undefined && stack [i]! = false) {
cetak (this.vertexlist [stack [i]]);
}
}
}
// fungsi topsorthelper ()
fungsi topsorthelper (v, dikunjungi, stack) {
mengunjungi [v] = true;
untuk masing -masing (var w di this.adj [v]) {
if (! Visit [w]) {
this.topsorthelper (dikunjungi [w], dikunjungi, stack);
}
}
stack.push (v);
}