Jenis Grafik dalam Struktur & Aplikasi Data

pengantar

Grafik adalah struktur non-linear yang terdiri dari node dan edge. Itu dapat mencakup kumpulan node yang terbatas atau tidak terbatas yang dipegang oleh tepi yang menghubungkan sepasang node. Struktur data adalah bagian penting dari setiap konsep pengkodean; dengan demikian, memiliki pemahaman yang kuat tentang berbagai jenis grafik dalam struktur data dapat membantu Anda melalui masalah dunia nyata yang kompleks.

Di dunia sekarang ini, data adalah kekuatan. Dengan demikian, mengatur data secara efisien untuk akses mudah sangat penting bagi setiap programmer. Pengetahuan tentang struktur data dan ragam grafiknya memberdayakan keterampilan pengkodean Anda untuk menargetkan masalah dunia nyata dan memberikan solusinya secara efektif.

Pelajari ilmu data untuk mendapatkan keunggulan atas pesaing Anda

Mari kita lihat berbagai jenis grafik yang biasa digunakan dalam struktur data dan bagaimana penerapannya dalam kehidupan nyata.

Jenis Grafik dalam Struktur Data

Struktur data adalah standar penyimpanan data praktis untuk semua bahasa, seperti struktur data grafik python atau struktur data grafik java. Menguasai semua jenis grafik harus menjadi prioritas bagi siapa pun yang ingin mempelajari struktur data. Karena teori graf memiliki banyak aplikasi kehidupan nyata, mereka menjadi sangat penting dalam struktur data.

Berbagai jenis grafik dalam struktur Data dapat dicantumkan di bawah ini:

1. Grafik Null

Seperti namanya, grafik nol kosong; dengan kata lain, itu adalah grafik tanpa tepi. Ini hanya terdiri dari simpul terisolasi dalam grafik dengan set tepi kosong.

2. Graf Hingga

Jika jumlah sisi dan simpul terdiri dari bilangan berhingga dalam suatu graf, maka graf tersebut dikenal sebagai graf berhingga.

3. Grafik Tak Terbatas

Jika seseorang tidak dapat memasukkan angka hingga ke jumlah node dan jumlah tepi dalam grafik, grafik tersebut dikenal sebagai grafik tak terbatas. Grafik tak terbatas tidak dapat dihitung, yang berarti Anda tidak dapat menghitung jumlah simpul atau tepi dalam jenis grafik ini.

4. Grafik Sederhana

Graf dikatakan sederhana bila hanya ada satu sisi di antara sepasang simpul. Dengan demikian, dua node dihubungkan oleh satu sisi dalam grafik, yang dapat mengidentifikasi hubungan yang pasti di antara keduanya.

5. Multi Grafik

Jika sepasang simpul dihubungkan dengan banyak sisi dalam suatu graf, maka graf tersebut dikenal sebagai graf multi. Grafik multi tidak terdiri dari loop sendiri. Ada dua jenis sisi yang bisa eksis dalam multi-graf. Mereka:

• Tepi Paralel

Sisi yang berjalan paralel, seperti dua jalan paralel dari satu sumber ke tujuan yang sama, dikenal sebagai sisi paralel.

• Lingkaran

Ini adalah sisi yang simpul sumber dan tujuannya sama.

Periksa AS - Program Ilmu Data kami

6. Grafik Berarah

Graf dikatakan berarah jika semua sisi yang ada di antara dua simpul atau simpul memiliki arah yang ditentukan. Grafik berarah juga dikenal sebagai digraf. Kita dapat menentukan simpul awal dan simpul akhir dengan melihat grafik berarah. Ingat, semua sisi dalam graf berarah harus berarah untuk disebut graf berarah.

7. Grafik Tidak Berarah

Suatu graf dikatakan graf tidak berarah jika simpul awal dan simpul akhir sulit ditentukan hanya dengan melihat ujung-ujungnya. Sama seperti graf berarah, sisi-sisinya harus tidak berarah agar bisa disebut graf tidak berarah.

8. Grafik Terhubung

Grafik terhubung adalah grafik di mana setidaknya ada satu jalur di antara semua node. Dalam istilah yang lebih sederhana, jika Anda memulai dari sebuah simpul dalam grafik yang terhubung, Anda harus dapat mengunjungi setiap simpul yang ada dalam grafik. Oleh karena itu, harus ada setidaknya satu jalur untuk setiap node.

9. Grafik Terputus

Dalam graf jenis ini, tidak ada tepi di antara sepasang simpul atau simpul. Jadi, tidak seperti graf terhubung, mencapai semua simpul dari sembarang simpul tidak dimungkinkan. Jika ada pasangan simpul yang tidak memiliki jalur di antara keduanya, itu disebut grafik terputus.

10. Grafik Lengkap

Sebuah graf dianggap lengkap jika ada sisi di antara setiap simpul, artinya sebuah sisi akan menghubungkan semua simpul dalam graf. Graf lengkap pada n simpul dilambangkan dengan Kn , dan jumlah sisi dalam graf tersebut adalah nC2 .

11. Grafik Siklik

Grafik harus memiliki setidaknya satu komponen siklik untuk dianggap sebagai grafik siklik. Sebaliknya, jika grafik tidak mengandung siklus apa pun, itu dianggap sebagai grafik asiklik.

12. Grafik Reguler

Dalam grafik biasa, semua simpul harus memiliki derajat yang sama. Derajat suatu simpul dapat didefinisikan sebagai jumlah simpul yang terhubung dengannya. Jadi, dalam graf biasa, semua node harus terhubung ke jumlah node yang sama.

13. Grafik Bipartit

Untuk grafik menjadi bipartit, itu harus memenuhi kriteria berikut.

• Grafik harus dibagi menjadi set simpul.
• Tepi hanya boleh terbentuk di antara satu kelompok node ke sisi lainnya. Aturan ini mencegah koneksi antara dua simpul dari kumpulan simpul yang sama.
• Kedua kelompok tidak boleh memiliki simpul yang sama di antara mereka.

Grafik yang mengikuti semua aturan di atas harus dianggap sebagai grafik bipartit.

14. Graf Berlabel

Tepi dalam grafik dapat diberi bobot. Bobot yang terkait dengan tepi dapat dipahami sebagai biaya perjalanan melalui tepi tersebut. Nilai-nilai ini dapat didasarkan pada parameter tetap dan dapat berubah di antara grafik. Sekarang, jika semua sisi memiliki bobot yang terkait dengannya, maka graf tersebut dapat disebut graf berlabel.

15. Grafik Asiklik Terarah

Grafik asiklik berarah adalah kombinasi dari grafik berarah dan asiklik di mana sisi-sisi berarah dari grafik tidak membentuk siklus apa pun. Sebaliknya, graf siklik berarah adalah graf dengan sisi-sisi berarah yang membentuk sebuah siklus.

Penerapan Graf dalam Struktur Data

Aplikasi graf yang paling menonjol dalam ilmu komputer adalah representasi aliran komputasi. Beberapa kasus grafik terkenal lainnya adalah:

1. Peta Google

Di Google Maps, struktur data grafik menentukan dan menghitung sistem transportasi. Ketika sebuah jalan bertemu dengan jalan lain dan membentuk persilangan, itu dianggap sebagai simpul, dan jalan di antara dua simpul tersebut diperlakukan sebagai tepi. Karenanya, Google Maps menemukan Anda cara terpendek dan tercepat ke tujuan Anda menggunakan struktur data grafik.

2. Facebook

Facebook menggunakan grafik tak terarah untuk mengidentifikasi pengguna dan teman pengguna. Setiap pengguna diperlakukan sebagai simpul, dan koneksi yang bergabung dengan mereka sebagai teman adalah tepi jaringan. Dengan algoritme berdasarkan struktur data grafik, Facebook menyarankan "orang yang mungkin Anda kenal" dan menampilkan "teman yang sama".

3. Web di seluruh dunia

World Wide Web adalah contoh grafik berarah. Itu juga merupakan ide dasar di balik sistem peringkat Google. Dalam sistem World Wide Web, setiap situs web dan aplikasi web diperlakukan sebagai simpul atau simpul, dan tautan dari satu situs web ke situs web lainnya dianggap sebagai tepi.

4. Sistem Operasi

Sistem operasi adalah kasus Grafik Alokasi Sumber Daya yang populer digunakan yang menggunakan setiap proses dan sumber daya sebagai node atau simpul. Tepi terjadi antara sumber daya ke proses yang dialokasikan atau dari proses permintaan ke sumber daya yang diminta. Terkadang siklus ini dapat membentuk loop tak terbatas, menginisialisasi kebuntuan.

5. Sistem Pemetaan

GPS Anda adalah kasus grafik yang populer digunakan untuk menemukan restoran, toko, dan tempat terdekat yang Anda pilih untuk dicari dengan bantuan teknologi ini.

6.Microsoft Excel

Grafik Asiklik Terarah atau DAG digunakan di Microsoft Excel.

7. Algoritma Dijkstra

Algoritma Dijkstra menggunakan struktur data graf untuk mengidentifikasi jalur terpendek antara dua, atau dalam beberapa kasus, lebih dari dua node.

8. Jaringan Penerbangan:

Komputasi jaringan penerbangan yang dioptimalkan adalah aplikasi nyata lainnya dari struktur data grafik. Jika Anda menganggap bandara sebagai simpul dan rute sebagai ujungnya, data tersebut sangat sesuai dengan kriteria grafik. Itulah sebabnya dengan bantuan berbagai algoritme yang ditingkatkan, rute terbaik antara dua bandara atau node ditentukan.

Ini adalah berbagai aplikasi grafik dalam struktur data , yang digunakan di seluruh dunia dalam berbagai aplikasi dan sistem untuk mengatur dan mempertahankan kelancaran fungsinya,

Mulailah perjalanan Anda sebagai ilmuwan data

Jika Anda ingin menjadi ilmuwan data dan menangani data dengan bijaksana menggunakan berbagai grafik yang kami pelajari, lihat berbagai kursus ilmu data di upGrad. Salah satu kursus yang paling populer adalah kursus PG-IIITB tentang Ilmu Data , kursus yang sangat baik untuk calon ilmuwan data pemula untuk memulai!

Inilah yang ditawarkan kursus ini.

• Dukungan karir 360 derajat dari pakar dan mentor industri
• Pengalaman langsung dengan Proyek Industri dan studi kasus terperinci untuk mengukur kemajuan reguler
• Berjejaring dengan pakar ilmu data di semua sektor, secara global

Anda juga dapat memeriksa semua kursus upGrad lainnya tentang Ilmu Data .