Struktur data bukan linear terdiri daripada pengumpulan unsur-unsur yang diedarkan pada satah yang bermaksud tidak ada urutan sedemikian di antara elemen-elemen yang ada dalam struktur data linier.
Carta Perbandingan
| Asas untuk perbandingan | Pokok | Grafik |
|---|---|---|
| Jalan | Hanya satu antara dua titik. | Lebih daripada satu laluan dibenarkan. |
| Nod akar | Ia mempunyai satu nod akar. | Graf tidak mempunyai nod akar. |
| Gelung | Tiada gelung dibenarkan. | Grafik boleh mempunyai gelung. |
| Kerumitan | Kurang kompleks | Lebih rumit berbanding |
| Teknik Traversal | Pre-order, In-order dan Post-order. | Carian terlebih dahulu dan carian terdahulu. |
| Bilangan tepi | n-1 (di mana n adalah bilangan nod) | Tidak ditakrifkan |
| Jenis model | Hierarki | Rangkaian |
Definisi Pokok
Pokok adalah koleksi item data yang biasanya dipanggil sebagai nod. Seperti yang dinyatakan di atas bahawa pokok adalah struktur data bukan linear yang menyusun item data dalam urutan yang disusun. Ia digunakan untuk menunjukkan struktur hierarki antara pelbagai elemen data dan menganjurkan data ke dalam cawangan yang menghubungkan maklumat tersebut. Penambahan kelebihan baru dalam hasil pokok dalam pembentukan gelung atau litar.
Terdapat beberapa jenis pokok seperti pokok binari, pokok carian binari, pokok AVL, pokok binari yang diiringi, B-pohon, dan sebagainya. Mampatan data, penyimpanan fail, manipulasi ungkapan aritmetik dan pokok permainan adalah sebahagian daripada penggunaan pokok struktur data.
Sifat pokok:
- Terdapat nod yang ditetapkan di bahagian atas pokok yang dikenali sebagai akar pokok.
- Baki data yang tersisa dibahagikan kepada subseksyen disjoint merujuk sebagai subtree.
- Pokoknya diperluas tinggi ke arah bawah.
- Pokok mesti disambungkan yang bermakna mesti ada jalan dari satu akar ke semua nod lain.
- Ia tidak mengandungi apa-apa gelung.
- Pokok mempunyai n-1 tepi.
Terdapat pelbagai istilah yang dikaitkan dengan pokok-pokok seperti nod terminal, kelebihan, tahap, darjah, kedalaman, hutan, dan sebagainya. Antara istilah-istilah tersebut, sebahagiannya diterangkan di bawah.
- Edge - Baris yang menghubungkan dua nod.
- Tahap - Pokok dibahagikan kepada tahap seperti nod akar berada pada tahap 0. Kemudian, anak-anak terdekat berada pada tahap 1, dan anak-anak terdekat berada pada tahap 2 dan seterusnya ke terminal atau nod daun.
- Ijazah - Ini adalah bilangan subtek nod dalam pokok tertentu.
- Kedalaman - Ia adalah paras maksima bagi setiap nod dalam suatu pokok tertentu dan juga dikenali sebagai ketinggian .
- Node terminal - Nod tahap tertinggi adalah nod terminal manakala nod lain kecuali terminal dan nod akar dikenali sebagai nod bukan terminal.
Takrifan Graf
Grafik juga merupakan struktur data non-linear matematik yang boleh mewakili pelbagai jenis struktur fizikal. Ia terdiri daripada kumpulan simpul (atau simpul) dan set tepi yang menghubungkan dua simpul. Verteks pada graf diwakili sebagai titik atau bulatan dan tepi ditunjukkan sebagai arka atau segmen garisan. Kelebihan diwakili oleh E (v, w) di mana v dan w ialah pasangan simpang. Pembuangan pinggir dari litar atau graf yang bersambung mencipta subgraph yang merupakan pokok.
Grafik diklasifikasikan ke dalam pelbagai kategori seperti yang diarahkan, tidak diarahkan, disambungkan, tidak disambungkan, mudah dan berbilang graf. Rangkaian komputer, sistem pengangkutan, graf rangkaian sosial, litar elektrik dan perancangan projek adalah beberapa aplikasi struktur data graf. Ia juga digunakan dalam teknik pengurusan yang dinamakan sebagai PERT (teknik evaluasi program dan kajian semula) dan CPM (kaedah laluan kritikal) di mana struktur grafik dianalisis.
Sifat graf:
- Titik dalam graf boleh dihubungkan dengan mana-mana bilangan simpul lain menggunakan tepi.
- Kelebihan boleh diarahkan atau diarahkan.
- Kelebihan boleh ditimbang.
Dalam graf juga kita menggunakan pelbagai istilah seperti simpang bersebelahan, laluan, kitaran, ijazah, graf bersambung, graf lengkap, graf berwajaran, dan lain-lain. Mari kita fahami beberapa istilah ini.
- Garis bersebelahan - Garis a adalah bersebelahan dengan titik b jika terdapat kelebihan (a, b) atau (b, a).
- Path - Jalan dari sudut pandang acak w ialah urutan bersebelahan.
- Kitaran - Ia adalah jalan di mana simpang pertama dan terakhir adalah sama.
- Ijazah - Ia adalah beberapa kejadian di pinggir.
- Grafik yang disambungkan - Jika terdapat laluan dari rentetan rawak ke mana-mana puncak lain, maka graf tersebut dikenali sebagai graf yang disambungkan.
Perbezaan Utama Antara Pokok dan Grafik
- Di dalam pokok terdapat hanya satu jalan di antara mana-mana dua simpang manakala graf boleh mempunyai laluan unidirectional dan dwiarah antara nod.
- Di dalam pokok itu, terdapat satu nod akar, dan setiap kanak-kanak boleh mempunyai hanya satu orang ibu bapa. Sebaliknya, dalam graf, tiada konsep nod akar.
- Pokok tidak boleh mempunyai gelung dan gelung diri sementara graf boleh mempunyai gelung dan gelung diri.
- Graf lebih rumit kerana ia boleh mempunyai gelung dan gelung diri. Sebaliknya, pokok adalah mudah berbanding dengan graf.
- Pokoknya dilalui menggunakan teknik pra-pesanan, pesanan dalam dan pasca pesanan. Di sisi lain, untuk grafik traversal, kami menggunakan BFS (Carian Breadth First) dan DFS (Kedalaman Pertama Carian).
- Pokok boleh mempunyai n-1 tepi. Sebaliknya, dalam graf, tidak ada bilangan tepi yang telah dipratentukan, dan ia bergantung kepada graf.
- Pokok mempunyai struktur hierarki manakala graf mempunyai model rangkaian.
Kesimpulannya
Graf dan pokok adalah struktur data bukan linear yang digunakan untuk menyelesaikan pelbagai masalah kompleks. Grafik adalah sekumpulan simpang dan pinggir di mana kelebihannya menghubungkan sepasang simpul sedangkan sebuah pohon dianggap sebagai graf minimum yang disambungkan yang mesti disambungkan dan bebas dari gelung.
