Struktur Data JavaScript dan Algoritma Graf dan Graf Algoritma_Pengetahuan Asas

Takrifan graf

Graf terdiri daripada set bucu tak kosong terhingga dan set tepi antara bucu Ia biasanya dinyatakan sebagai: G(V,E), dengan G mewakili graf dan V ialah bucu graf G. . Set, E ialah set tepi dalam graf G.

Graf terarah

Tepi berarah: Jika tepi dari bucu Vi ke Vj mempunyai arah, maka tepi ini dipanggil tepi terarah, juga dipanggil lengkok (Lengkok), diwakili oleh pasangan tertib , Vi dipanggil ialah ekor arka, dan Vj dipanggil kepala arka.

Graf tidak tertib

Tepi tidak berarah: Jika tepi antara bucu Vi dan Vj tidak mempunyai arah, tepi ini dipanggil tepi tidak berarah (Tepi) dan diwakili oleh pasangan tidak tertib (Vi, Vj).

Gambar ringkas

Graf mudah: Dalam struktur graf, jika tiada tepi dari bucu ke dirinya sendiri, dan tepi yang sama tidak muncul berulang kali, maka graf sedemikian dipanggil graf ringkas.

Grafik

mewakili bucu

Langkah pertama dalam mencipta kelas graf ialah mencipta kelas Vertex untuk menyimpan bucu dan tepi. Fungsi kelas ini adalah sama dengan kelas Node senarai terpaut dan pepohon carian binari. Kelas Vertex mempunyai dua ahli data: satu yang mengenal pasti bucu, dan nilai Boolean yang menunjukkan sama ada ia telah dilawati. Mereka dinamakan label dan wasVisited masing-masing.

Salin kod Kod adalah seperti berikut:

fungsi Vertex(label){
This.label = label;
}

Kami menyimpan semua bucu dalam tatasusunan, dan dalam kelas graf, mereka boleh dirujuk oleh kedudukan mereka dalam tatasusunan

mewakili kelebihan

Maklumat sebenar graf disimpan pada "tepi" kerana ia menerangkan struktur graf. Nod induk pokok binari hanya boleh mempunyai dua nod anak, tetapi struktur graf adalah lebih fleksibel.

Kami memanggil kaedah mewakili tepi graf sebagai senarai bersebelahan atau tatasusunan senarai bersebelahan. Ia akan menyimpan tatasusunan yang terdiri daripada senarai bucu bersebelahan sesuatu bucu

Rajah pembinaan

Tentukan kelas Graf seperti berikut:

Salin kod Kod adalah seperti berikut:

fungsi Graf(v){
This.vertices = v;//vertices titik tertinggi
This.edges = 0;
This.adj = [];
for(var i =0;I This.adj[i] = [];
This.adj[i].push('');
}
This.addEdge = addEdge;
This.toString = toString;
}

Kelas ini merekodkan bilangan tepi yang diwakili oleh graf dan merekodkan bilangan bucu menggunakan panjang dan bilangan bucu dalam graf.

Salin kod Kod adalah seperti berikut:

fungsi addEdge(){
This.adj[v].push(w);
This.adj[w].push(v);
This.edges ;
}

Di sini kita menggunakan gelung for untuk menambah sub-tatasusunan pada setiap elemen dalam tatasusunan untuk menyimpan semua bucu bersebelahan dan memulakan semua elemen kepada rentetan kosong.

Perjalanan graf

Perjalanan mendalam-pertama

DepthFirstSearch, juga dikenali sebagai carian depth-first, dirujuk sebagai DFS.

Contohnya, jika anda mencari kunci di dalam bilik, anda boleh mulakan dari mana-mana bilik Cari sudut, meja sisi katil, katil, bawah katil, almari pakaian, kabinet TV dan lain-lain di dalam bilik satu persatu. , supaya tidak terlepas mana-mana Dead ends, selepas mencari semua laci dan kabinet penyimpanan, kemudian cari bilik sebelah.

Kedalaman carian pertama:

Carian pertama mendalam ialah melawati bucu yang belum dilawati, menandainya sebagai dilawati, dan kemudian mengakses bucu lain yang belum dilawati secara rekursif dalam senarai bersebelahan bucu awal

Tambah tatasusunan pada kelas Graf:

Salin kod Kod adalah seperti berikut:

this.marked = [];//Simpan bucu yang dilawati
for(var i=0;i This.marked[i] = false;//Dimulakan kepada false
}

Fungsi carian mendalam-pertama:

Salin kod Kod adalah seperti berikut:

fungsi dfs(v){
This.marked[v] = true;
//Pernyataan if tidak diperlukan di sini
If(this.adj[v] != undefined){
​​print("Puncak yang dilawati: " v );
untuk setiap (var w dalam ini.adj[v]){
Jika(!ini.ditandakan[w]){
This.dfs(w);
            }
}
}
}

Pencarian luas didahulukan

Breadth-first search (BFS) ialah kaedah carian buta yang bertujuan untuk mengembangkan dan memeriksa semua nod dalam graf secara sistematik untuk mencari hasil. Dalam erti kata lain, ia tidak mengambil kira kemungkinan lokasi hasil dan mencari keseluruhan graf dengan teliti sehingga keputusan ditemui.

Carian keluasan didahulukan bermula dari bucu pertama dan cuba melawat bucu sedekat mungkin dengannya, seperti yang ditunjukkan di bawah:

Prinsip kerjanya ialah:

1. Mula-mula cari bucu yang belum dilawati bersebelahan dengan bucu semasa dan tambahkannya pada senarai bucu yang dilawati dan baris gilir; 2. Kemudian ambil bucu v seterusnya daripada graf dan tambahkannya pada senarai bucu yang dilawati
3. Akhir sekali, tambahkan semua bucu yang belum dilawati bersebelahan dengan v pada baris gilir
Berikut ialah takrifan fungsi carian luas pertama:

Salin kod Kod adalah seperti berikut:

bfs(s) fungsi{
var baris gilir = [];
This.marked = benar;
Queue.push(s);//Tambah pada penghujung baris gilir
While(queue.length>0){
          var v = queue.shift();//Alih keluar daripada kepala baris gilir
If(v == undefined){
                                      print("Puncak yang dilawati: " v);
}
untuk setiap (var w dalam ini.adj[v]){
Jika(!ini.ditandakan[w]){
This.edgeTo[w] = v;
This.marked[w] = true;
queue.push(w);
            }
}
}
}

Laluan terpendek

Apabila melakukan carian luas pertama, laluan terpendek dari satu bucu ke satu bucu bersambung ditemui secara automatik

Tentukan laluan

Untuk mencari laluan terpendek, anda perlu mengubah suai algoritma carian pertama keluasan untuk merekodkan laluan dari satu bucu ke bucu lain Kami memerlukan tatasusunan untuk menyimpan semua tepi dari satu bucu ke bucu seterusnya tepi tatasusunanKepada

Salin kod Kod adalah seperti berikut:

this.edgeTo = [];//Tambah baris ini pada kelas Graf

//fungsi bfs
bfs(s) fungsi{
var baris gilir = [];
This.marked = benar;
Queue.push(s);//Tambah pada penghujung baris gilir
While(queue.length>0){
          var v = queue.shift();//Alih keluar daripada kepala baris gilir
If(v == undefined){
                                      print("Puncak yang dilawati: " v);
}
untuk setiap (var w dalam ini.adj[v]){
Jika(!ini.ditandakan[w]){
This.edgeTo[w] = v;
This.marked[w] = true;
queue.push(w);
            }
}
}
}

Algoritma pengisihan topologi

Isihan topologi akan mengisih semua bucu graf terarah supaya tepi terarah menghala dari bucu sebelumnya ke bucu kemudian.
Algoritma pengisihan topologi adalah serupa dengan BFS Perbezaannya ialah algoritma pengisihan topologi tidak serta-merta mengeluarkan bucu yang dilawati Sebaliknya, ia melawati semua bucu bersebelahan dalam senarai bucu semasa tidak akan ditolak senarai itu habis dalam timbunan.

Algoritma pengisihan topologi dibahagikan kepada dua fungsi Fungsi pertama ialah topSort(), yang digunakan untuk menyediakan proses pengisihan dan memanggil fungsi tambahan topSortHelper(), dan kemudian memaparkan senarai puncak yang diisih

.

Kerja utama algoritma pengisihan topologi diselesaikan dalam fungsi rekursif topSortHelper(). Akhirnya, puncak semasa ditolak ke tindanan.

Salin kod Kod adalah seperti berikut:

//topSort() fungsi
fungsi topSort(){
timbunan var = [];
var dilawati = [];
for(var i =0;i         melawati[i] = palsu;
}
for(var i = 0;i Jika(dilawati[i] == palsu){
This.topSortHelper(i,visited,stack);
}
}
for(var i = 0;i Jika(timbunan[i] !=tidak ditentukan && tindanan[i] != palsu){
​​​​​print(this.vertexList[tindanan[i]]);
}
}
}

//topSortHelper() fungsi
fungsi topSortHelper(v,dilawati,tindan){
dilawati[v] = benar;
untuk setiap (var w dalam ini.adj[v]){
Jika(!melawat[w]){
This.topSortHelper(dilawati[w],dilawati,tindan);
}
}
​ stack.push(v);
}