Grafik dalam Struktur Data: Jenis, Penyimpanan & Traversal

Struktur data adalah cara yang efisien untuk mengatur data dalam ilmu data sehingga data dapat diakses dengan mudah dan digunakan secara efektif. Ada banyak jenis database, tetapi mengapa grafik memainkan peran penting dalam manajemen data dibahas dalam artikel ini.

Peringatan spoiler: Anda menggunakan Grafik dalam struktur data setiap hari untuk mengambil rute terbaik ke kantor Anda, mendapatkan saran untuk makan siang, menonton film, dan mengoptimalkan rute penerbangan Anda berikutnya. Kedengarannya menarik! Mari kita lihat tentang sifat-sifat grafik dan aplikasinya.

Pertama, mari kita lihat apa itu Graf? Ini adalah representasi data dalam struktur non-linier yang terdiri dari node (atau simpul) dan tepi (atau jalur).

Grafik dalam struktur data dapat disebut sebagai struktur data yang terdiri dari data yang disimpan di antara banyak kelompok tepi (jalur) dan simpul (simpul), yang saling berhubungan. Struktur data grafik (N, E) disusun dengan kumpulan Node dan Edges. Baik node maupun vertex harus berhingga.

Pada representasi graf di atas, Himpunan Simpul adalah N={0,1,2,3,4,5,6}dan himpunan rusuknya adalah

G={01,12,23,34,45,05,03}

Sekarang mari kita pelajari jenis-jenis graf.

Baca: 10 Teknik Visualisasi Data Teratas

Jenis Grafik

1. Grafik Berbobot

Graf yang sisi atau jalurnya memiliki nilai. Semua nilai yang terlihat terkait dengan tepi disebut bobot. Nilai tepi dapat mewakili berat/biaya/panjang.

Nilai atau bobot juga dapat mewakili:

• Jarak yang ditempuh antara dua titik- Contoh: Untuk mencari jalur terpendek ke kantor, jarak antara dua workstation dalam jaringan kantor.
• Kecepatan paket data dalam suatu jaringan atau bandwidth.

2. Graf Tak Berbobot

Di mana tidak ada nilai atau bobot yang terkait dengan tepi. Secara default, semua grafik tidak berbobot kecuali ada nilai yang terkait.

3. Grafik Tidak Berarah

Di mana satu set objek terhubung, dan semua tepinya dua arah. Gambar di bawah ini menunjukkan grafik tidak berarah,

Ini seperti asosiasi dua pengguna Facebook setelah terhubung sebagai teman. Kedua pengguna dapat merujuk dan berbagi foto, saling berkomentar.

4. Grafik Berarah

Juga disebut digraf, di mana satu set objek (N, E) terhubung, dan semua tepi diarahkan dari satu simpul ke simpul lainnya. Gambar di atas menampilkan grafik berarah.

Checkout: Proyek Visualisasi Data yang Dapat Anda Replikasi

Penyimpanan Grafik

Setiap metode penyimpanan memiliki kelebihan dan kekurangannya, dan metode penyimpanan yang tepat dipilih berdasarkan kerumitannya. Dua struktur data yang paling umum digunakan untuk menyimpan grafik adalah:

1. Daftar kedekatan

Di sini node disimpan sebagai indeks dari array satu dimensi diikuti oleh edge yang disimpan sebagai daftar.

2. Matriks ketetanggaan

Di sini node direpresentasikan sebagai indeks dari array dua dimensi, diikuti oleh tepi yang direpresentasikan sebagai nilai bukan nol dari matriks yang berdekatan.

Baik baris dan kolom menampilkan Node; seluruh matriks diisi dengan "0" atau "1", yang mewakili benar atau salah. Nol menyatakan bahwa tidak ada jalur, dan 1 mewakili jalur.

Grafik Traversal

Graph traversal adalah metode yang digunakan untuk mencari node dalam sebuah graph. Graf traversal digunakan untuk menentukan urutan yang digunakan untuk pengaturan node. Itu juga mencari edge tanpa membuat loop, yang berarti semua node dan edge dapat dicari tanpa membuat loop.

Ada dua struktur traversal graf.

1. DFS (Depth First Search): Metode pencarian mendalam

Pencarian DFS dimulai dari node pertama dan berjalan lebih dalam dan lebih dalam, menjelajah ke bawah hingga node yang ditargetkan ditemukan. Jika kunci yang ditargetkan tidak ditemukan, jalur pencarian diubah ke jalur yang dihentikan penjelajahan selama pencarian awal, dan prosedur yang sama diulang untuk cabang itu.

Pohon rentang dihasilkan dari hasil pencarian ini. Metode pohon ini tanpa loop. Jumlah total node dalam struktur data stack digunakan untuk mengimplementasikan traversal DFS.

Langkah-langkah yang diikuti untuk mengimplementasikan pencarian DFS:

Langkah 1 – Ukuran tumpukan perlu ditentukan tergantung pada jumlah total node.

Langkah 2 – Pilih simpul awal untuk transversal; itu perlu didorong ke tumpukan dengan mengunjungi simpul itu.

Langkah 3 – Sekarang, kunjungi node yang berdekatan yang tidak dikunjungi sebelumnya dan dorong ke stack.

Langkah 4 – Ulangi Langkah 3 sampai tidak ada node berdekatan yang tidak dikunjungi.

Langkah 5 – Gunakan backtracking dan satu node ketika tidak ada node lain yang akan dikunjungi.

Langkah 6 – Kosongkan tumpukan dengan mengulangi langkah 3,4, dan 5.

Langkah 7 – Ketika tumpukan kosong, pohon merentang akhir dibentuk dengan menghilangkan tepi yang tidak digunakan.

Aplikasi DFS adalah:

• Memecahkan teka-teki dengan hanya satu solusi.
• Untuk menguji apakah suatu graf bipartit.
• Penyortiran Topologi untuk menjadwalkan pekerjaan dan banyak lainnya.

2. BFS (Breadth-First Search): Pencarian diimplementasikan menggunakan metode antrian

Breadth-First Search menavigasi grafik dalam gerakan luas dan memanfaatkan berdasarkan Antrian untuk melompat dari satu node ke node lain, setelah menemukan ujung di jalur.

Langkah-langkah yang diikuti untuk mengimplementasikan pencarian BFS,

Langkah 1 – Berdasarkan jumlah node, Queue didefinisikan.

Langkah 2 – Mulai dari simpul traversal mana pun. Kunjungi simpul itu dan tambahkan ke Antrian.

Langkah 3 – Sekarang periksa node berdekatan yang tidak dikunjungi, yang ada di depan Antrian, dan tambahkan itu ke Antrian, bukan ke awal.

Langkah 4 – Sekarang mulailah menghapus node yang tidak memiliki edge yang perlu dikunjungi dan tidak ada dalam Queue.

Langkah 5 – Kosongkan Antrian dengan mengulangi langkah 4 dan 5.

Langkah 6 – Hapus tepi yang tidak digunakan dan bentuk pohon rentang hanya setelah Antrian kosong.

Aplikasi BFS adalah:

• Jaringan Peer to Peer- Seperti di Bittorrent, ini digunakan untuk menemukan semua node yang berdekatan.
• Perayap di Mesin Pencari.
• Situs Jejaring Sosial dan banyak lagi.

Aplikasi Dunia Nyata Grafik dalam Struktur Data

Grafik digunakan dalam banyak aplikasi sehari-hari seperti representasi jaringan (jalan, pemetaan serat optik, perancangan papan sirkuit, dll.). Contoh: Dalam jaringan data Facebook, node mewakili pengguna, foto atau komentarnya, dan tepi mewakili foto, komentar pada foto.

Grafik dalam struktur data memiliki aplikasi yang luas. Beberapa yang menonjol adalah:

• API Grafik Sosial – Ini adalah cara utama data dikomunikasikan masuk dan keluar dari platform media sosial Facebook. Ini adalah API berbasis HTTP, yang digunakan untuk meminta data secara terprogram, mengunggah foto dan video, membuat cerita baru, dan banyak tugas lainnya. Ini terdiri dari node, tepi, dan bidang; untuk query, node objek tertentu digunakan. Tepi untuk sekelompok objek yang tunduk pada satu objek dan bidang digunakan untuk mengambil data tentang setiap objek di antara grup.
• API GraphQL Yelp – Ini adalah mesin rekomendasi yang digunakan untuk mengambil data spesifik dari platform Yelp. Di sini, perintah digunakan untuk menemukan tepi, setelah itu node tertentu diminta untuk mengambil hasil yang tepat. Ini mempercepat proses pengambilan.

Pada platform Yelp, node mewakili bisnis, berisi id, nama, is_closed, dan banyak properti grafik lainnya.

• Algoritma Path Optimization- Mereka digunakan untuk menemukan koneksi terbaik yang sesuai dengan kriteria kecepatan, keamanan, bahan bakar, dll. BFS digunakan dalam algoritma ini. Contoh terbaik adalah Google Maps Platform (Maps, Routes APIs).
• Jaringan Penerbangan- Dalam jaringan penerbangan, ini digunakan untuk menemukan jalur yang dioptimalkan yang sesuai dengan struktur data grafik . Ini juga membantu dalam model dan mengoptimalkan prosedur bandara secara efisien.

Baca Juga: Manfaat Visualisasi Data

Kesimpulan

Pada artikel ini, pertama-tama kita membahas definisi Graph dan Graph dalam struktur data dan kemudian mempelajari tentang jenis-jenis graf dengan propertinya. Kemudian, kita belajar tentang metode yang umum digunakan untuk penyimpanan grafik diikuti dengan metode pencarian topik penting yang digunakan dalam Graphs, Graph Traversal. Akhirnya, kami membahas aplikasi dunia nyata dari struktur data grafik.

Artikel ini memberikan wawasan tentang Grafik dalam struktur data ; pengetahuan tentang ini sangat penting untuk pemahaman mendasar dalam basis data Grafik, implementasi algoritma pencarian, pemrograman, dan banyak lagi. Itu harus dipelajari dari pakar industri.

Mengapa Memilih Kursus dengan upGrad ?

Kami menyarankan Anda untuk memilih Program PG Eksekutif dalam Ilmu Data yang ditawarkan oleh IIIT Bangalore yang dihosting di upGrad karena di sini Anda bisa mendapatkan pertanyaan 1-1 dengan instruktur kursus. Ini tidak hanya berfokus pada pembelajaran teoretis tetapi juga memberikan pentingnya pengetahuan berbasis praktis, yang penting untuk menyiapkan pelajar untuk menghadapi proyek dunia nyata dan memberi Anda sertifikat NASSCOM 1 India, yang membantu Anda mendapatkan pekerjaan bergaji tinggi di Ilmu Data.

Karya dikutip

Departemen Matematika/CS – Beranda , www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/11-Graph/data-stru.html.

“Wawasan Matematika.” Definisi Grafik Terarah – Math Insight , mathinsight.org/definition/directed_graph.

Singh, Amritpal. “Struktur Data Grafik.” Sedang , Sedang, 29 Maret 2020, medium.com/@singhamritpal49/graph-data-structure-49427c81b3b3.

Solo. “Aplikasi Kehidupan Nyata dari Struktur Data Grafik yang Harus Anda Ketahui.” Grafik Data dan GraphQL API Development-Leap Graph , leapgraph.com/graph-data-structures-applications.