Doğrusal olmayan bir veri yapısı, bir düzlem üzerinde dağılmış olan elemanların bir koleksiyonundan oluşur; bu, doğrusal bir veri yapısında var olduğu gibi, elemanlar arasında böyle bir sekans olmadığı anlamına gelir.
Karşılaştırma Tablosu
| Karşılaştırma için temel | ağaç | grafik |
|---|---|---|
| yol | İki köşe arasında sadece bir tane var. | Birden fazla yola izin verilir. |
| Kök düğümü | Tam olarak bir kök düğümü var. | Grafikte kök düğümü yok. |
| döngüler | Hiçbir döngüye izin verilmez. | Grafikte döngüler olabilir. |
| karmaşa | Daha az kompleks | Karşılaştırmalı olarak daha karmaşık |
| Geçiş teknikleri | Ön sipariş, Sipariş ve Sipariş. | Genişlik ilk arama ve derinlik ilk arama. |
| Kenar sayısı | n-1 (burada n düğüm sayısıdır) | Tanımlanmamış |
| Model türü | Hiyerarşik | Ağ |
Ağacın tanımı
Ağaç, genellikle düğüm olarak adlandırılan veri öğelerinin sonlu bir koleksiyonudur. Yukarıda belirtildiği gibi bir ağacın veri öğelerini sıralı düzende düzenleyen doğrusal olmayan bir veri yapısı olduğu belirtilir. Çeşitli veri elemanları arasında hiyerarşik bir yapı göstermek için kullanılır ve verileri bilgiyle ilişkilendiren dallar halinde düzenler. Bir ağaca yeni bir kenarın eklenmesi, halka veya devrenin oluşumuna yol açar.
İkili ağaç, ikili arama ağacı, AVL ağacı, dişli ikili ağaç, B ağacı, vb. Gibi çeşitli ağaç türleri vardır. Veri sıkıştırma, dosya depolama, aritmetik ifadelerin manipülasyonu ve oyun ağaçları, ağaç uygulamalarından bazılarıdır. veri yapısı.
Ağacın Özellikleri:
- Ağacın tepesinde, ağacın kökü olarak bilinen bir düğüm vardır.
- Kalan veri maddeleri ayrık alt gruplara bölünmüştür alt ağaç olarak adlandırılır.
- Ağaç yüksekliği aşağıya doğru genişletilir.
- Bir ağaç bağlanmalı, bu da bir kökten diğer tüm düğümlere doğru bir yol olması gerektiği anlamına gelir.
- Herhangi bir döngü içermez.
- Bir ağacın n-1 kenarları vardır.
Terminal düğümü, kenar, seviye, derece, derinlik, orman vs. gibi ağaçlar ile ilgili çeşitli terimler vardır. Bu terimler arasında, bazıları aşağıda açıklanmıştır.
- Kenar - İki düğümü birleştiren bir çizgi.
- Seviye - Bir ağaç, kök düğümü 0 düzeyinde olacak şekilde seviyelere ayrılır. O zaman, acil çocukları seviye 1'de olur ve acil çocukları seviye 2'de ve böylece terminal veya yaprak düğümüne kadar gider.
- Derecesi - Belirli bir ağaçtaki bir düğümün alt ağaç sayısıdır.
- Derinlik - Belirli bir ağaçtaki herhangi bir düğümün maksimum seviyesidir ve aynı zamanda yükseklik olarak da bilinir.
- Terminal düğümü - En üst seviye düğüm terminal düğümüdür, terminal ve kök düğümü dışındaki diğer düğümler terminal olmayan düğümler olarak bilinir.
Grafiğin tanımı
Grafik aynı zamanda çeşitli fiziksel yapı türlerini temsil edebilen matematiksel doğrusal olmayan bir veri yapısıdır. Bir grup köşeden (veya düğümler) ve iki köşeyi birbirine bağlayan bir dizi kenardan oluşur. Grafikteki tepe noktaları nokta veya daire şeklinde ve kenarlar yay veya çizgi parçası olarak gösterilir. Bir kenar, E (v, w) ile temsil edilir, burada v ve w, köşe çiftleridir. Bir devre veya bağlı grafikten bir kenarın çıkarılması ağaç olan bir alt yazı oluşturur.
Grafikler, yönlendirilmiş, yönlendirilmemiş, bağlı, bağlı olmayan, basit ve çoklu grafik gibi çeşitli kategorilere ayrılmıştır. Bilgisayar ağı, ulaşım sistemi, sosyal ağ grafiği, elektrik devreleri ve proje planlaması grafik veri yapısının uygulamalarından bazılarıdır. Ayrıca grafik yapısının analiz edildiği PERT (program değerlendirme ve inceleme tekniği) ve CPM (kritik yol yöntemi) olarak adlandırılan yönetim tekniğinde de kullanılır.
Grafiğin özellikleri:
- Grafikteki bir köşe, kenarları kullanarak herhangi bir sayıda başka köşe noktasına bağlanabilir.
- Bir kenar yönlendirilebilir veya yönlendirilebilir.
- Bir kenar ağırlıklandırılabilir.
Grafikte ayrıca bitişik köşeler, yol, çevrim, derece, bağlı grafik, tam grafik, ağırlıklı grafik vb. Gibi çeşitli terimler kullanıyoruz. Bu terimlerden bazılarını anlayalım.
- Bitişik köşeler - Bir köşe (a, b) veya (b, a) varsa, köşe b'ye köşeye bitişiktir.
- Yol - rastgele bir tepe noktasından bir yol w bitişik bir köşe dizisidir.
- Döngü - İlk ve son köşelerin aynı olduğu bir yoldur.
- Derece - Bir tepe üzerinde meydana gelen bir dizi kenardır.
- Bağlantılı grafik - Rastgele bir tepe noktasından başka bir tepe noktasına bir yol varsa, o zaman grafik bağlı bir grafik olarak bilinir.
Ağaç ve Grafik Arasındaki Temel Farklılıklar
- Bir ağaçta, herhangi iki köşe arasında yalnızca bir yol bulunur, oysa grafiğin düğümler arasında tek yönlü ve çift yönlü yolları olabilir.
- Ağaçta, tam olarak bir kök düğümü vardır ve her çocuğun yalnızca bir ebeveyni olabilir. Karşıt olarak, bir grafikte kök düğüm kavramı yoktur.
- Bir ağaç ilmeklere ve kendi ilmeklere sahip olamaz, oysa grafik ilmeklere ve kendi ilmeklere sahip olabilir.
- Grafikler, döngüler ve kendi öz döngüleri olabileceğinden daha karmaşıktır. Buna karşılık, ağaçlar grafiğe göre daha basittir.
- Ağaç, sıralı, sıralı ve sıralı teknikler kullanılarak travers edilir. Öte yandan, grafik geçişi için, BFS (İlk önce Ekmek Arama) ve DFS (İlk Önce Derinlik Arama) kullanıyoruz.
- Bir ağaç n-1 kenarlara sahip olabilir. Aksine, grafikte önceden tanımlanmış sayıda kenar yoktur ve grafiğe bağlıdır.
- Bir ağaç hiyerarşik bir yapıya sahipken, grafik bir ağ modeline sahiptir.
Sonuç
Grafik ve ağaç, çeşitli karmaşık problemleri çözmek için kullanılan doğrusal olmayan veri yapısıdır. Bir grafik, bir kenarın bir çift köşeyi birbirine bağladığı bir köşe ve kenar grubudur; oysa bir ağaç, bağlanması ve halkalar içermesi gereken asgari derecede bağlı bir grafik olarak kabul edilir.
