Kenali struktur data yang anda gunakan setiap hari
? Selamat datang! Mari Mulakan dengan Beberapa Konteks Vital. Izinkan saya bertanya sesuatu kepada anda:
✅ Adakah anda menggunakan Carian Google?
✅ Adakah anda menggunakan Peta Google?
✅ Adakah anda menggunakan laman media sosial?
Sekiranya jawapan anda adalah "ya" untuk salah satu daripada soalan ini, anda pasti menggunakan grafik dan anda bahkan tidak mengetahuinya! Terkejut? ? Saya juga! Artikel ini akan memberi anda pengenalan visual kepada dunia grafik, tujuan, elemen, dan jenisnya.
Struktur data ini benar-benar menarik perhatian saya kerana kemampuannya yang luar biasa. Mereka sangat kuat sehingga anda tidak akan membayangkan betapa beragamnya aplikasi dunia nyata mereka. Mari kita mulakan! ?
? Aplikasi Dunia Nyata - Keajaiban Bermula!
Grafik digunakan dalam pelbagai industri dan bidang:
- Sistem GPS dan Peta Google menggunakan grafik untuk mencari jalan terpendek dari satu destinasi ke destinasi yang lain.
- Rangkaian Sosial menggunakan grafik untuk mewakili hubungan antara pengguna.
- Algoritma Carian Google menggunakan grafik untuk menentukan kesesuaian hasil carian.
- Penyelidikan Operasi adalah bidang yang menggunakan grafik untuk mencari jalan yang optimum untuk mengurangkan kos pengangkutan dan penghantaran barang dan perkhidmatan.
- Malah Kimia menggunakan grafikuntuk mewakili molekul !!! ❤️
Aplikasi mereka sangat mengagumkan, bukan?
Mari mulakan perjalanan kita ke dunia ini! ?
? Temui Grafik!
Sekarang setelah anda mempunyai beberapa konteks, mari mulakan dengan membincangkan tujuan dan elemen utama mereka.
Grafik digunakan untuk mewakili, mencari, menganalisis, dan mengoptimumkan hubungan antara elemen (rumah, lapangan terbang, lokasi, pengguna, artikel, dll.).
Ini adalah contoh rupa grafik:
? Blok Bangunan
Saya pasti anda melihat dua elemen utama dalam rajah di atas: bulatan dan garis tebal yang menghubungkannya. Mereka dipanggil, masing-masing, Node dan Edges .
Mari lihat mereka dengan lebih terperinci! ?
- Node: mereka adalah elemen yang membuat rangkaian. Mereka boleh mewakili rumah, lokasi, lapangan terbang, pelabuhan, perhentian bas, bangunan, pengguna, pada dasarnya apa sahaja yang dapat anda gambarkan sebagai terhubung dengan elemen lain yang serupa dalam rangkaian.
- Tepi: mereka adalah hubungan antara nod. Mereka boleh mewakili jalan, penerbangan, laluan bas, hubungan antara dua pengguna dalam rangkaian sosial, atau apa pun yang mungkin mewakili hubungan antara node dalam konteks yang sedang anda gunakan.
? Apa Yang Berlaku Sekiranya Tidak Ada Sambungan?
Sekiranya dua nod tidak dihubungkan oleh tepi, itu bermakna tidak ada hubungan langsung di antara mereka. Tetapi jangan panik! Might Anda mungkin masih boleh pergi dari satu simpul ke simpul yang lain dengan mengikuti urutan tepi, sama seperti memandu melalui beberapa jalan untuk sampai ke destinasi akhir anda. ?️ ? ?
Sebagai contoh, dalam rajah di bawah, walaupun tidak ada hubungan langsung ( tepi ) antara simpul ungu (kiri) dan simpul kuning (kanan), anda boleh pergi dari simpul ungu ke simpul oren, ke nod merah jambu, ke nod hijau, dan akhirnya mencapai nod kuning. ?
Ini adalah aspek utama grafik, yang mana anda dapat mencari elemen yang anda cari dengan mengikuti jalan yang tersedia.
? Notasi & Terminologi
Sangat penting untuk belajar "bahasa" formal untuk bekerja dengan grafik:
|V|= Jumlah bucu ( nod ) dalam grafik.|E|= Jumlah sambungan ( tepi ) dalam grafik.
Dalam contoh di bawah, |V| = 6kerana terdapat enam nod (bulatan) dan
|E| = 7kerana terdapat tujuh tepi (garisan).
? Jenis Grafik
Grafik dikelaskan berdasarkan ciri pinggirnya (sambungan). Mari kita perhatikan secara terperinci! ?
1️⃣ Graf yang diarahkan
Dalam graf yang diarahkan, tepi mempunyai arah. Mereka pergi dari satu simpul ke simpul yang lain, dan tidak ada cara untuk kembali ke simpul awal melalui tepi itu.
Seperti yang anda lihat dalam rajah di bawah, tepi (sambungan) kini mempunyai anak panah yang menunjuk ke arah tertentu. Fikirkan tepi ini sebagai jalan sehala. Anda boleh pergi ke satu arah dan sampai ke destinasi anda, tetapi anda tidak dapat kembali melalui jalan yang sama, jadi anda perlu mencari jalan alternatif.
? Contohnya, jika kita membuat grafik untuk perkhidmatan penghantaran pizza, yang mewakili sebuah kota, dua rumah (simpul) mungkin dihubungkan dengan jalan sehala (tepi). Anda boleh sampai dari rumah A ke rumah B melalui jalan ini, tetapi anda tidak dapat kembali, jadi anda perlu mengambil jalan alternatif.
? Catatan: Dalam grafik yang diarahkan, anda mungkin tidak dapat kembali sama sekali ke lokasi awal anda sekiranya tidak ada jalan dengan arah yang sesuai. ? Dalam rajah di bawah, anda dapat melihat bahawa anda berjaya pergi dari simpul ungu ke simpul hijau, tetapi perhatikan bahawa tidak ada cara untuk kembali dari simpul hijau ke simpul ungu kerana pinggirnya adalah "jalan sehala. "
2️⃣ Graf Tidak Terarah
Dalam grafik jenis ini, tepi tidak diarahkan (mereka tidak mempunyai arah tertentu). Fikirkan tepi yang tidak diarahkan sebagai jalan dua arah. Anda boleh pergi dari satu simpul ke simpul yang lain dan kembali melalui "jalan" yang sama.
? Catatan: Apabila anda melihat gambarajah grafik di mana tepinya tidak mempunyai anak panah yang menunjuk ke arah tertentu, anda dapat menganggap bahawa grafik tersebut tidak diarahkan.
? Untuk perkhidmatan penghantaran pizza kami, ini bermaksud bahawa motosikal penghantaran boleh pergi dari sumber ke destinasi melalui jalan atau jalan yang sama (Untuk melegakan mereka! ?).
Dalam grafik di bawah, anda boleh pergi dari simpul ungu ke simpul hijau dan kembali melalui jalan yang sama , sehingga anda tidak mencapai titik yang tidak akan kembali. ?
? Berat? - Ya, Berat!
Graf wajaran 1️⃣
Dalam graf wajaran, setiap pinggir mempunyai nilai yang berkaitan dengannya (dipanggil berat) . Nilai ini digunakan untuk mewakili hubungan tertentu yang dapat diukur antara nod yang mereka sambungkan.
Sebagai contoh, bobot dapat mewakili jarak, waktu, jumlah sambungan yang dikongsi antara dua pengguna dalam rangkaian sosial, atau apa pun yang dapat digunakan untuk menggambarkan hubungan antara nod dalam konteks yang sedang Anda kerjakan.
Berat ini digunakan oleh Algoritma Dijkstra untuk mengoptimumkan laluan dengan mencari jalan terpendek atau paling murah antara nod dalam rangkaian. (Nantikan artikel mengenai Algoritma Dijkstra! ?).
2️⃣ Graf Tidak Berat
Sebaliknya, grafik yang tidak berwajaran tidak mempunyai berat yang berkaitan dengan pinggirnya. Contoh grafik jenis ini boleh didapati di rangkaian sosial, di mana tepi mewakili hubungan antara dua pengguna. Sambungan tidak dapat dihitung. Oleh itu, tepi tidak mempunyai berat.
? Catatan: Anda mungkin menyedari bahawa, setakat ini, grafik kami hanya mempunyai satu tepi yang menghubungkan setiap pasangan nod. Adalah wajar untuk bertanya sama ada terdapat lebih dari satu tepi antara sepasang nod. Secara kebetulan, ini mungkin dilakukan dengan ultigraf M ! T hey boleh mempunyai pelbagai sisi yang menghubungkan sepasang nod yang sama.
? Bilangan Tepi! - Faktor Penting
Sangat penting untuk mengetahui apakah grafik mempunyai banyak atau sedikit sisi kerana ini adalah faktor penting untuk menentukan bagaimana anda akan mewakili struktur data ini dalam kod anda. Mari lihat pelbagai jenis! ?
1️⃣ Grafik Padat
Grafik padat mempunyai banyak sisi. Tapi tunggu! I️ Saya tahu apa yang mesti anda fikirkan, bagaimana anda dapat menentukan apa yang memenuhi syarat sebagai "banyak kelebihan"? Ini sedikit terlalu subjektif, bukan? ? Saya setuju dengan anda, jadi mari kita menghitungnya sedikit:
? Mari cari bilangan tepi maksimum dalam graf yang diarahkan. Sekiranya terdapat |V|nod dalam graf yang diarahkan (dalam contoh di bawah, enam nod), itu bermaksud bahawa setiap nod boleh mempunyai |v|sambungan (dalam contoh di bawah, enam sambungan).
Kenapa? Kerana setiap nod berpotensi terhubung dengan semua nod lain dan dengan sendirinya (lihat "loop" di bawah) . Oleh itu, yang Kapasiti maksimum tepi yang graf boleh mempunyai adalah|V|*|V| , iaitu jumlah bilangan nod didarab dengan bilangan maksimum sambungan yang setiap nod boleh mempunyai.
Apabila bilangan tepi dalam grafik mendekati bilangan tepi maksimum, grafiknya padat. ?
? Catatan: "Gelung" berlaku apabila simpul mempunyai tepi yang menghubungkannya dengan dirinya sendiri. Pelik dan menarik, bukan? ?
2️⃣ Grafik Jarang
Graf Sparse mempunyai beberapa sisi. Seperti yang anda lihat dalam rajah di bawah, tidak banyak hubungan antara nod.
Apabila bilangan pinggir dalam grafik jauh lebih sedikit daripada bilangan tepi maksimum, grafiknya jarang. ?
⭕️ Jumpa Kitaran!
Sekarang mari kita lihat konsep penting untuk memahami grafik, kitaran.
Anda mungkin menyedari bahawa jika anda mengikuti urutan sambungan dalam grafik, anda mungkin akan menemui jalan yang akan membawa anda kembali ke simpul yang sama. Ini seperti "berjalan berputar-putar", seolah-olah anda sedang berkeliling kota dan anda mengambil jalan yang dapat membawa anda kembali ke lokasi awal anda.
Dalam grafik, jalur "bulat" ini disebut "kitaran". Ia adalah jalan yang sah yang bermula dan berakhir pada simpul yang sama. Contohnya, dalam rajah di bawah, anda dapat melihat bahawa jika anda memulakan di mana-mana nod, anda boleh kembali ke simpul yang sama dengan mengikuti pinggirnya.
Siklus tidak selalu "diasingkan" kerana boleh menjadi sebahagian daripada graf yang lebih besar. Anda dapat mengesannya dengan memulakan carian anda pada simpul tertentu dan mencari jalan yang membawa anda kembali ke simpul yang sama.
? Ringkasnya…
- Grafik adalah struktur data yang hebat yang anda gunakan setiap hari melalui Carian Google, Peta Google, GPS, dan media sosial.
- Mereka digunakan untuk mewakili elemen yang berkongsi hubungan .
- Unsur-unsur dalam grafik dipanggil Nodes dan hubungan di antara mereka disebut Edges .
- Grafik dapat diarahkan, ketika tepinya memiliki orientasi tertentu, mirip dengan jalan satu arah, atau tidak diarahkan, ketika tepinya tidak memiliki orientasi tertentu, mirip dengan jalan dua arah.
- Tepi boleh mempunyai nilai yang berkaitan dengannya, disebut berat .
- Sekiranya graf mempunyai banyak sisi, ia dipanggil grafik padat . Jika tidak, jika ia mempunyai sedikit sisi, ia dipanggil graf jarang .
- Serangkaian sambungan dapat membentuk kitaran jika mereka membuat jalan yang membolehkan anda kembali ke simpul yang sama.
Teruskan belajar mengenai struktur data yang luar biasa ini! Ia sangat bernilai untuk masa depan anda sebagai pemaju. Saya sedang belajar mengenai struktur data sekarang, dan saya rasa ia sangat menarik. ? ? ❤️
Yang penting jangan berhenti menyoal. Rasa ingin tahu mempunyai alasan tersendiri untuk wujud. - Albert Einstein? Terima kasih!
Saya sangat berharap anda menyukai artikel saya. ❤️
Ikut sayaTwitter. ?