Seorang programmer yang efektif membutuhkan pemahaman yang kuat tentang struktur data dan algoritma. Wawancara teknis akan sering menguji kemampuan pemecahan masalah dan berpikir kritis Anda.
Grafik adalah salah satu dari banyak struktur data penting dalam pemrograman. Dalam kebanyakan kasus, memahami grafik dan memecahkan masalah berbasis grafik tidak mudah.
Apa itu grafik, dan apa yang perlu Anda ketahui tentangnya?
Apa Itu Grafik?
Graf adalah struktur data non-linier yang memiliki simpul (atau simpul) dengan tepi yang menghubungkannya. Semua pohon adalah subtipe dari graf, tetapi tidak semua graf adalah pohon, dan graf adalah struktur data dari mana pohon berasal.
Meskipun kamu bisa membangun struktur data dalam JavaScript dan bahasa lainnya, Anda dapat menerapkan grafik dengan berbagai cara. Pendekatan yang paling populer adalah daftar tepi, daftar kedekatan, dan matriks ketetanggaan.
Itu Panduan Khan Academy untuk merepresentasikan grafik adalah sumber yang bagus untuk belajar tentang cara merepresentasikan grafik.
Ada banyak jenis grafik. Satu perbedaan umum adalah antara diarahkan dan tidak terarah grafik; ini banyak muncul dalam tantangan pengkodean dan penggunaan di kehidupan nyata.
Jenis Grafik
- Grafik terarah: Graf yang semua sisinya memiliki arah, disebut juga dwihuruf.
- Grafik tak berarah: Graf tak berarah disebut juga graf dua arah. Dalam grafik tidak berarah, arah tepi tidak menjadi masalah, dan traversal dapat menuju ke segala arah.
- Grafik tertimbang: Graf berbobot adalah graf yang simpul dan sisinya memiliki nilai yang berasosiasi. Dalam kebanyakan kasus, nilai ini mewakili biaya untuk menjelajahi simpul atau tepi tersebut.
- Grafik terbatas: Graf yang memiliki jumlah simpul dan sisi berhingga.
- Grafik tak terbatas: Graf yang memiliki jumlah simpul dan sisi yang tidak terbatas.
- Grafik sepele: Graf yang hanya memiliki satu simpul dan tidak memiliki sisi.
- Grafik sederhana: Jika hanya satu sisi yang menghubungkan setiap pasangan simpul dari suatu graf, maka disebut graf sederhana.
- Grafik nol: Graf nol adalah graf yang tidak memiliki sisi yang menghubungkan simpul-simpulnya.
- Multigraf: Dalam multigraf, setidaknya sepasang simpul memiliki lebih dari satu sisi yang menghubungkannya. Dalam multigraf, tidak ada self-loop.
- grafik lengkap: Graf lengkap adalah graf yang setiap simpulnya terhubung ke setiap simpul lain dalam graf tersebut. Ia juga dikenal sebagai grafik penuh.
- Grafik semu: Graf yang memiliki loop sendiri di samping sisi-sisi graf lainnya disebut graf semu.
- Grafik reguler: Graf beraturan adalah graf yang semua simpulnya memiliki derajat yang sama; yaitu setiap node memiliki jumlah tetangga yang sama.
- Grafik terhubung: Grafik terhubung hanyalah grafik apa pun di mana dua simpul terhubung; yaitu grafik dengan setidaknya satu jalur antara setiap dua node grafik.
- Grafik terputus: Graf tak terhubung adalah kebalikan langsung dari graf terhubung. Pada graf tidak terhubung, tidak ada sisi yang menghubungkan simpul-simpul graf tersebut, seperti pada a batal grafik.
- Grafik siklik: Graf siklik adalah graf yang memuat paling sedikit satu siklus graf (jalur yang berakhir di titik awal graf tersebut).
- Grafik asiklik: Graf asiklik adalah graf yang tidak memiliki siklus sama sekali. Itu bisa diarahkan atau tidak diarahkan.
- Subgraf: Subgraf adalah graf turunan. Adalah graf yang terbentuk dari simpul dan sisi yang merupakan himpunan bagian dari graf lain.
SEBUAH lingkaran dalam graf adalah sisi yang berawal dari sebuah simpul dan berakhir pada simpul yang sama. Oleh karena itu, putaran diri adalah perulangan hanya pada satu simpul graf, seperti yang terlihat pada graf semu.
Algoritma Graf Traversal
Menjadi jenis struktur data non-linear, melintasi grafik cukup rumit. Melintasi grafik berarti melewati dan menjelajahi setiap simpul yang diberikan ada jalur yang valid melalui tepi. Algoritma traversal grafik terutama terdiri dari dua jenis.
- Pencarian Breadth-First (BFS): Breadth-first search adalah algoritme penjelajahan graf yang mengunjungi simpul graf dan menjelajahi tetangganya sebelum melanjutkan ke simpul turunannya. Meskipun Anda dapat mulai melintasi grafik dari simpul mana pun yang dipilih, simpul akar biasanya merupakan titik awal yang disukai.
- Pencarian Depth-First (DFS): Ini adalah algoritma traversal grafik utama kedua. Ia mengunjungi simpul grafik dan menjelajahi simpul atau cabang turunannya sebelum melanjutkan ke simpul berikutnya—yaitu, masuk lebih dulu sebelum melebar.
Breadth-first search adalah algoritma yang direkomendasikan untuk menemukan jalur antara dua node secepat mungkin, terutama jalur terpendek.
Pencarian mendalam-pertama sebagian besar direkomendasikan ketika Anda ingin mengunjungi setiap node dalam grafik. Kedua algoritme traversal berfungsi dengan baik dalam kasus apa pun, tetapi yang satu mungkin lebih sederhana dan lebih dioptimalkan daripada yang lain dalam skenario yang dipilih.
Ilustrasi sederhana dapat membantu memahami kedua algoritme dengan lebih baik. Pikirkan negara bagian suatu negara sebagai grafik dan coba periksa apakah dua negara bagian, X dan kamu, terhubung. Pencarian mendalam-pertama mungkin berjalan di jalan hampir di seluruh negeri tanpa menyadari cukup awal bahwa kamu hanya 2 negara bagian dari X.
Keuntungan dari pencarian luas-pertama adalah bahwa ia mempertahankan kedekatan dengan node saat ini sebanyak mungkin sebelum pergi ke yang berikutnya. Ini akan menemukan hubungan antara X dan kamu dalam waktu singkat tanpa harus menjelajahi seluruh negeri.
Perbedaan utama lainnya antara kedua algoritma ini adalah cara mereka diimplementasikan dalam kode. Pencarian luas-pertama adalah sebuah algoritma berulang dan menggunakan antre, sedangkan pencarian mendalam-pertama biasanya diimplementasikan sebagai algoritma rekursif yang memanfaatkan tumpukan.
Di bawah ini adalah beberapa pseudocode yang menunjukkan implementasi kedua algoritma.
Pencarian Luas-Pertama
bfs (Grafik G, akar GraphNode) {
membiarkan q be baru Antre// tandai root sebagai dikunjungi
root.visited = BENAR// tambahkan root ke antrian
q.antrian(akar)
ketika (q bukan kosong) {
membiarkan saat ini menjadi q.dequeue() // hapus elemen depan dalam antrian
untuk (tetangga n arus di G) {
jika (n adalahbukan belum dikunjungi) {
// tambahkan ke antrian - sehingga Anda dapat menjelajahi tetangganya juga
q.antrian(n)
n.dikunjungi = BENAR
}
}
}
}
Pencarian Kedalaman-Pertama
dfs (Grafik G, akar GraphNode) {
// kasus dasar
jika (akar adalah batal) kembali// tandai root sebagai dikunjungi
root.visited = BENAR
untuk (tetangga n dari akar di G)
jika (n adalahbukan belum dikunjungi)
dfs (G, n) // panggilan rekursif
}
Beberapa algoritma traversal grafik lainnya berasal dari pencarian luas-pertama dan kedalaman-pertama. Yang paling populer adalah:
- Pencarian dua arah: Algoritma ini adalah cara yang dioptimalkan untuk menemukan jalur terpendek antara dua node. Ini menggunakan dua pencarian luas-pertama yang bertabrakan jika ada jalan.
- Jenis topologi: Ini digunakan dalam grafik berarah untuk mengurutkan node dalam urutan yang diinginkan. Anda tidak dapat menerapkan pengurutan topologi ke grafik tidak berarah atau grafik dengan siklus.
- Algoritma Dijkstra: Ini juga merupakan jenis BFS. Hal ini juga digunakan untuk menemukan jalur terpendek antara dua node di a graf berarah berbobot, yang mungkin memiliki siklus atau tidak.
Pertanyaan Wawancara Umum Berdasarkan Grafik
Grafik termasuk yang penting struktur data yang harus diketahui setiap programmer. Pertanyaan sering muncul tentang topik ini dalam wawancara teknis, dan Anda mungkin menghadapi beberapa masalah klasik terkait dengan topik tersebut. Ini termasuk hal-hal seperti "hakim kota", "jumlah pulau", dan masalah "penjual keliling".
Ini hanyalah beberapa dari banyak masalah wawancara berbasis grafik yang populer. Anda dapat mencobanya di Kode Leet, Peringkat Peretas, atau GeeksforGeeks.
Memahami Struktur dan Algoritma Data Grafik
Grafik tidak hanya berguna untuk wawancara teknis. Mereka juga memiliki kasus penggunaan dunia nyata, seperti di jaringan, peta, dan sistem penerbangan untuk menemukan rute. Mereka juga digunakan dalam logika yang mendasari sistem komputer.
Grafik sangat baik untuk mengatur data dan membantu kita memvisualisasikan masalah yang kompleks. Grafik hanya boleh digunakan jika benar-benar diperlukan, untuk mencegah kompleksitas ruang atau masalah memori.
