Ağaç ve Grafik Arasındaki Fark
İçerik
Ağaç ve grafik, ağacın hiyerarşik bir yapıdaki düğümler arasındaki ilişkiyi temsil etmenin çok yararlı bir yolunu sunduğu doğrusal olmayan veri yapısı kategorisine girer ve grafik bir ağ modelini izler. Ağaç ve grafik, bir ağaç yapısının bağlanması gerektiği ve grafikte böyle bir kısıtlama olmadığı sürece hiçbir zaman döngüye sahip olamayacağı gerçeğiyle farklılaşır.
Doğrusal olmayan bir veri yapısı, bir düzlem üzerinde dağılmış olan elementlerin bir koleksiyonundan oluşur; bu, lineer bir veri yapısında var olduğu gibi elementler arasında böyle bir sekans olmadığı anlamına gelir.
-
- Karşılaştırma Tablosu
- Tanım
- Anahtar Farklılıklar
- Sonuç
Karşılaştırma Tablosu
| Karşılaştırma için temel | ağaç | grafik |
|---|---|---|
| Yol, yörünge | İ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. | Grafiğin bir 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ı
bir 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, döngü ya da devre oluşumu ile sonuçlanır.
İ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ü birbirine bağlayan bir çizgi.
- seviye - Bir ağaç, kök düğümü 0 düzeyinde olacak şekilde seviyelere ayrılır. O zaman, acil çocukları 1. seviyededir ve acil çocukları 2. seviyededir ve böylece terminal veya yaprak düğümüne kadar gider.
- Derece, aşama - 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 yükseklik.
- Terminal düğümü - En üst seviye düğüm terminal düğümdür, terminal ve kök düğüm dışındaki diğer düğümler terminal olmayan düğümler olarak bilinir.
Grafiğin tanımı
bir 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ştırma sistemi, sosyal ağ grafiği, elektrik devreleri ve proje planlaması grafik veri yapısının uygulamalarından bazılarıdır. Ayrıca olarak adlandırılan yönetim tekniğinde kullanılır. PERT (program değerlendirme ve inceleme tekniği) ve CPM grafik yapısının analiz edildiği (kritik yol yöntemi).
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 terimlerin bazılarını anlayalım.
- Bitişik köşeler - Bir köşe (a, b) veya (b, a) varsa, köşe b'ye bitişiktir.
- Yol, yörünge - Rasgele bir tepe noktasından w bir yol, bitişik bir köşe sırasıdır.
- Döngü - İlk ve son köşelerin aynı olduğu bir yoldur.
- Derece, aşama - Bir tepe üzerinde meydana gelen bir dizi kenardır.
- Bağlı grafik - Rastgele bir köşeden başka bir köşeye giden bir yol varsa, o zaman grafik bağlı bir grafik olarak bilinir.
- 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ç, halkalar ve kendi ilmeklerine sahip olamaz, bir grafik ise ilmeklere ve kendi ilmeklerine 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.
