Struktur data lanjutan. Bagian Satu: Grafik Acyclic Directional

Halo semuanya! Minggu depan, kelas akan dimulai pada kelompok baru kursus Algoritma untuk Pengembang . Dalam hal ini, kami membagikan kepada Anda terjemahan dari materi yang sangat kecil, namun agak menarik.

---

Saya ingin memulai seri artikel ini dengan struktur data yang kita semua kenal sebagai pengembang, tetapi mungkin saja kita bahkan tidak tahu cara kerjanya.

“Grafik asiklik terarah? Tidak pernah mendengar ini. Jangan berpikir bahwa Anda tahu segalanya tentang saya! ”, Anda dapat mengatakan, tetapi grafik inilah yang memungkinkan kontrol versi. Ya, Git adalah grafik asiklik. Pada artikel ini, saya akan berbagi dengan Anda pengetahuan tentang Directed Acyclic Graphs (DAGs), dan kemudian menunjukkan kepada Anda cara menulis Anda sendiri.

Apa itu DAG?

Jadi apa artinya itu? DAG adalah grafik searah di mana tidak ada elemen yang dapat dianggap sebagai anak. Banyak dari kita yang akrab dengan daftar, pohon, dan grafik yang ditautkan. DAG sangat mirip dengan yang pertama dan kedua dalam implementasi yang ketiga.


Itu terlihat seperti pohon, tetapi tidak cukup

Dalam bentuknya yang paling minimal, DAG memiliki 4 komponen:

1. Nodes Mereka menyimpan data.
2. Tepi Arah : Panah yang mengarah ke satu arah (yang membuat struktur data ini tidak seperti yang lain).
3. Satu simpul leluhur “hebat” tanpa orangtua . (Fakta menyenangkan: kebanyakan pohon leluhur sebenarnya adalah grafik asiklik yang diarahkan, bukan pohon, karena kadang-kadang "sepupu menikah satu sama lain")
4. Pergi Atau simpul tanpa simpul anak.

Mari kita tulis grafik asiklik terarah kita

Sekarang mari kita menulis kodenya. Pertama, buat konstruktor dengan dua properti dan beri nama DAG.

function DAG() { this.nodes = []; this.vertices = {}; } 

Buat metode untuk menambahkan node. Lihat apa yang saya lakukan di sini?

 DAG.prototype.add = function(node) { if (!node) { return; } if (this.vertices[node]) { return this.vertices[node]; } const vertex = { node: node, incoming: {}, incomingNodes: [], hasOutgoing: false, value: null }; this.vertices[node] = vertex; this.nodes.push(node); return vertex; }; 

Bagaimana cara kerjanya? Objek vertex adalah tempat semua keajaiban terjadi. Kami menambahkan node, objek dengan node yang masuk, dan array dengan semua namanya, variabel tipe Boolean yang memberi sinyal apakah node menunjuk ke sesuatu atau tidak, dan nilainya. Kami akan beralih ke ini nanti.

Sekarang mari kita tambahkan beberapa tepi dan menghubungkan node bersama. Sebelum kita dapat melakukan ini, kita harus membuat fungsi pembantu yang memeriksa apakah kita mengunjungi node ini atau tidak. Mari kita sebut visit .

 function visit(vertex, fn, visited, path) { const name = vertex.name, vertices = vertex.incoming, names = vertex.incomingNames, len = names.length, i; if (!visited) { visited = {}; } if (!path) { path = []; } if (visited.hasOwnProperty(name)) { return; } path.push(name); visited[name] = true; for (i = 0; i < len; i++) { visit(vertices[names[i]], fn, visited, path); } fn(vertex, path); path.pop(); } 

Berikut ini terjadi:

 DAG.prototype.addEdge = function(fromName, toName) { if (!fromName || !toName || fromName === toName) { return; } const from = this.add(fromName) const to = this.add(toName); if (to.incoming.hasOwnProperty(fromName)) { return; } function checkCycle(vertex, path) { if (vertex.name === toName) { throw new Error(“Theres a cycle foo!!!!!“)); } } visit(from, checkCycle); from.hasOutgoing = true; to.incoming[fromName] = from; to.incomingNames.push(fromName); }; 

Saatnya membayar upeti

Ketika saya sedang mempelajari bahan-bahan untuk menulis artikel ini, saya membaca beberapa pesan indah dari orang-orang luar biasa pintar, dan sebagai hasilnya, sebagian besar informasi diterima dari mereka. Saya mendapatkan beberapa informasi teoritis dari postingan yang terstruktur dengan baik pada DAG dan kontrol versi ini. Kode yang disajikan di sini terinspirasi oleh sumber barajs dan penulisnya. Dan saya belajar banyak dari artikel dan posting lain tentang DAG di blog banyak orang hebat.

Terima kasih sudah membaca!