graph implementation c using adjacency list
Bu Eğitim C ++ 'da Grafiklerin Uygulanmasını Açıklar. Ayrıca Grafiklerin Farklı Türleri, Gösterimleri ve Uygulamaları Hakkında Bilgi Edineceksiniz:
Grafik, doğrusal olmayan bir veri yapısıdır. Bir grafik, iki veya daha fazla köşeyi birbirine bağlayan 'köşeler' ve 'kenarlar' olarak da adlandırılan Düğümlerin bir koleksiyonu olarak tanımlanabilir.
Bir grafik ayrıca, köşelerin ebeveyn-çocuk ilişkisine sahip olmadığı ancak aralarında karmaşık bir ilişki sürdürdüğü döngüsel bir ağaç olarak da görülebilir.
ağ güvenlik anahtarı neye benzer
=> Absolute C ++ Eğitim Serisi İçin Tıklayınız.
Ne öğreneceksin:
C ++ 'da Grafik Nedir?
Yukarıda belirtildiği gibi, C ++ 'da bir grafik, köşeler ve kenarların bir koleksiyonu olarak tanımlanan doğrusal olmayan bir veri yapısıdır.
Aşağıda bir grafik veri yapısı örneği verilmiştir.
Yukarıda örnek bir G grafiği verilmiştir. Grafik G, bir köşe noktaları kümesidir {A, B, C, D, E} ve bir dizi kenar {(A, B), (B, C), (A, D), (D, E), (E, C), (B, E), (B, D)}.
Grafik Türleri - Yönlendirilmiş ve Yönlendirilmemiş Grafik
Kenarların yönlere sahip olmadığı bir grafiğe Yönlendirilmemiş grafik denir. Yukarıda gösterilen grafik, yönlendirilmemiş bir grafiktir.
Kenarların kendileriyle ilişkili yönlere sahip olduğu bir grafiğe Yönlü grafik denir.
Aşağıda, yönlendirilmiş bir grafik örneği verilmiştir.
Yukarıda gösterilen yönlendirilmiş grafikte, kenarlar sıralı bir çift oluşturur; burada her kenar, bir tepe noktasından diğerine belirli bir yolu temsil eder. Yolun başladığı tepe noktasına ' İlk Düğüm 'Yolun sona erdiği köşe ise' Terminal Düğümü ”.
Dolayısıyla, yukarıdaki grafikte, köşeler kümesi {A, B, C, D, E} ve kenar kümesi {(A, B), (A, D), (B, C), (B, E ), (D, E) (E, C)}.
Aşağıdaki grafikle ilişkili olarak kullanılan grafik terminolojisini veya ortak terimleri tartışacağız.
Grafik Terminolojisi
- Köşe: Grafiğin her düğümü bir köşe olarak adlandırılır. Yukarıdaki grafikte, A, B, C ve D grafiğin köşeleridir.
- Kenar: İki tepe arasındaki bağlantı veya yola kenar denir. İki veya daha fazla köşeyi birbirine bağlar. Yukarıdaki grafikteki farklı kenarlar AB, BC, AD ve DC'dir.
- Bitişik düğüm: Bir grafikte, iki düğüm bir kenarla bağlanırsa, bunlara bitişik düğümler veya komşular denir. Yukarıdaki grafikte, A ve B köşeleri AB kenarı ile bağlanmıştır. Böylece A ve B bitişik düğümlerdir.
- Düğümün derecesi: Belirli bir düğüme bağlı kenarların sayısına düğümün derecesi denir. Yukarıdaki grafikte, düğüm A, derece 2'ye sahiptir.
- Yol: Bir grafikte bir tepe noktasından diğerine gitmemiz gerektiğinde izlememiz gereken düğüm dizisine yol denir. Örnek grafiğimizde, A düğümünden C'ye gitmemiz gerekirse, yol A-> B-> C olacaktır.
- Kapalı yol: Başlangıç düğümü bir terminal düğümü ile aynıysa, bu yol kapalı yol olarak adlandırılır.
- Basit yol: Diğer tüm düğümlerin farklı olduğu kapalı bir yola basit yol denir.
- Döngü: Yinelenen kenarların veya tepe noktalarının olmadığı ve ilk ve son köşelerin aynı olduğu bir yola döngü denir. Yukarıdaki grafikte, A-> B-> C-> D-> A bir döngüdür.
- Bağlantılı Grafik: Bağlantılı bir grafik, köşelerin her biri arasında bir yolun olduğu grafiktir. Bu, izole edilmiş veya bağlantı kenarı olmayan tek bir tepe olmadığı anlamına gelir. Yukarıda gösterilen grafik bağlantılı bir grafiktir.
- Tam Grafik: Her düğümün diğerine bağlı olduğu bir grafiğe Tam grafik denir. Bir grafikteki toplam düğüm sayısı N ise, tam grafik N (N-1) / 2 sayıda kenar içerir.
- Ağırlıklı grafik: Her kenara, uzunluğunu (bir kenarla birbirine bağlanan köşeler arasındaki mesafeyi) gösteren pozitif bir değere ağırlık denir. Ağırlıklı kenarlar içeren grafiğe ağırlıklı grafik denir. Bir kenarın (e) ağırlığı, w (e) ile belirtilir ve bir kenarı geçmenin maliyetini gösterir.
- Diyagraf: Bir digraf, her kenarın belirli bir yönle ilişkilendirildiği ve geçişin yalnızca belirtilen yönde yapılabildiği bir grafiktir.
Grafik Gösterimi
Grafik veri yapısının bellekte depolanma şekline 'temsil' denir. Grafik, sıralı bir gösterim veya bağlantılı bir gösterim olarak saklanabilir.
Bu türlerin ikisi de aşağıda açıklanmıştır.
Sıralı Temsil
Grafiklerin sıralı gösteriminde, bitişik matris kullanıyoruz. Bitişik matris, n x n boyutunda bir matristir; burada n, grafikteki köşe sayısıdır.
Bitişik matrisin satırları ve sütunları, bir grafikteki köşeleri temsil eder. Köşeler arasında bir kenar olduğunda matris elemanı 1'e ayarlanır. Kenar mevcut değilse, eleman 0'a ayarlanır.
Aşağıda, bitişik matrisini gösteren örnek bir grafik verilmiştir.
Yukarıdaki grafik için bitişik matrisini gördük. Unutmayın ki bu yönsüz bir grafiktir ve kenarın her iki yönde de mevcut olduğunu söyleyebiliriz. Örneğin, AB kenarı mevcut olduğundan, kenar BA'nın da mevcut olduğu sonucuna varabiliriz.
Bitişik matriste, kenar mevcut olduğunda 1'e, kenar olmadığında 0'a ayarlanan matris elemanları olan köşelerin etkileşimlerini görebiliriz.
Şimdi yönlendirilmiş bir grafiğin bitişik matrisini görelim.
Yukarıda gösterildiği gibi, bitişik matris içindeki kesişme elemanı, ancak ve ancak bir tepe noktasından diğerine yönlendirilmiş bir kenar varsa 1 olacaktır.
Yukarıdaki grafikte, tepe A'dan iki kenarımız var. Bir kenar, tepe B ile sonlanırken, ikincisi tepe C ile sonlanır. Dolayısıyla, bitişik matriste A ve B'nin kesişimi, A ve C'nin kesişimi olarak 1'e ayarlanır.
Sonra, ağırlıklı grafiğin sıralı gösterimini göreceğiz.
Aşağıda, ağırlıklı grafik ve buna karşılık gelen bitişik matris verilmiştir.
Ağırlıklı bir grafiğin sıralı temsilinin diğer grafik türlerinden farklı olduğunu görebiliriz. Burada, bitişik matris içindeki sıfır olmayan değerler, kenarın gerçek ağırlığı ile değiştirilir.
AB kenarının ağırlığı = 4'tür, dolayısıyla bitişik matrisinde, A ve B'nin kesişimini 4'e ayarladık. Benzer şekilde, diğer tüm sıfır olmayan değerler ilgili ağırlıklarına değiştirilir.
Bitişiklik listesinin uygulanması ve takip edilmesi daha kolaydır. Geçiş, yani bir köşeden diğerine bir kenar olup olmadığını kontrol etmek O (1) zaman alır ve bir kenarın kaldırılması da O (1) alır.
Grafik ister seyrek (daha az kenar) ister yoğun olsun, her zaman daha fazla yer kaplar.
Bağlantılı Temsil
Yakınlık listesini grafiğin bağlantılı gösterimi için kullanıyoruz. Bitişik liste gösterimi, grafiğin her bir düğümünü ve bu düğüme bitişik olan düğümlere bir bağlantıyı korur. Tüm bitişik düğümleri geçtiğimizde, bir sonraki işaretçiyi listenin sonunda null olarak ayarlıyoruz.
Önce yönsüz bir grafiği ve onun bitişiklik listesini ele alalım.
Yukarıda gösterildiği gibi, her düğüm için bağlantılı bir listeye (bitişiklik listesi) sahibiz. A tepe noktasından B, C ve D köşelerine giden kenarlara sahibiz. Dolayısıyla, bu düğümler karşılık gelen bitişik listesindeki A düğümüne bağlanır.
Ardından, yönlendirilmiş grafik için bir bitişiklik listesi oluşturuyoruz.
Yukarıdaki grafikte, köşe E'den kaynaklanan hiçbir kenar olmadığını görüyoruz. Dolayısıyla, köşe E için bitişiklik listesi boştur.
Şimdi ağırlıklı grafik için bitişiklik listesini oluşturalım.
Ağırlıklı bir grafik için, yukarıda gösterildiği gibi kenarın ağırlığını belirtmek için bitişik liste düğümüne fazladan bir alan ekliyoruz.
örnekle ilkel ve kruskal algoritması
Bitişiklik listesine tepe noktası eklemek daha kolaydır. Ayrıca bağlantılı liste uygulaması nedeniyle yerden tasarruf sağlar. Bir tepe noktası arasında bir kenar olup olmadığını bulmamız gerektiğinde, işlem verimli değildir.
Grafikler İçin Temel İşlemler
Grafik veri yapısı üzerinde gerçekleştirebileceğimiz temel işlemler şunlardır:
- Bir köşe ekleyin: Grafiğe tepe noktası ekler.
- Bir kenar ekleyin: Bir grafiğin iki köşesi arasına bir kenar ekler.
- Grafik köşelerini görüntüleyin: Bir grafiğin köşelerini görüntüleyin.
Bitişiklik Listesini Kullanarak C ++ Grafik Uygulaması
Şimdi, bitişiklik listesini kullanarak basit bir grafiği göstermek için bir C ++ uygulaması sunuyoruz.
Burada ağırlıklı yönelimli bir grafik için bitişiklik listesini görüntüleyeceğiz. Yakınlık listesini ve grafiğin kenarlarını tutmak için iki yapı kullandık. Bitişiklik listesi (başlangıç_vertex, bitiş_vertex, ağırlık) olarak görüntülenir.
C ++ programı aşağıdaki gibidir:
#include using namespace std; // stores adjacency list items struct adjNode { int val, cost; adjNode* next; }; // structure to store edges struct graphEdge { int start_ver, end_ver, weight; }; class DiaGraph{ // insert new nodes into adjacency list from given graph adjNode* getAdjListNode(int value, int weight, adjNode* head) { adjNode* newNode = new adjNode; newNode->val = value; newNode->cost = weight; newNode->next = head; // point new node to current head return newNode; } int N; // number of nodes in the graph public: adjNode **head; //adjacency list as array of pointers // Constructor DiaGraph(graphEdge edges(), int n, int N) { // allocate new node head = new adjNode*(N)(); this->N = N; // initialize head pointer for all vertices for (int i = 0; i Çıktı:
Çıktı:
Grafik bitişiklik listesi
(başlangıç_vertex, bitiş_vertex, ağırlık):
(0, 2, 4) (0, 1, 2)
(1, 4, 3)
(2, 3, 2)
(3, 1, 4)
(4, 3, 3)
Grafik Uygulamaları
Grafiklerin bazı uygulamalarını tartışalım.
- Grafikler, bilgisayar biliminde ağ grafiklerini veya anlamsal grafikleri tasvir etmek veya hatta hesaplama akışını tasvir etmek için yaygın olarak kullanılır.
- Derleyicilerde, kaynakların süreçlere tahsisini göstermek veya veri akışı analizini vb. Göstermek için grafikler yaygın olarak kullanılır.
- Grafikler, bazı özel derleyicilerde veritabanı dillerinde sorgu optimizasyonu için de kullanılır.
- Sosyal ağ sitelerinde, grafikler insan ağını tasvir eden temel yapılardır.
- Ulaşım sistemini, özellikle de karayolu ağını oluşturmak için yaygın olarak grafikler kullanılır. Popüler bir örnek, tüm dünyada yol tariflerini belirtmek için yoğun şekilde grafikler kullanan Google haritalarıdır.
Sonuç
Grafik, diğer alanların yanı sıra bilgisayar bilimi alanında da birçok uygulamaya sahip, popüler ve yaygın olarak kullanılan bir veri yapısıdır. Grafikler, iki veya daha fazla köşeyi birbirine bağlayan köşelerden ve kenarlardan oluşur.
Bir grafik yönlendirilebilir veya yönsüz olabilir. Doğrusal bir temsil olan bitişik matrisini ve bitişik bağlantılı listeyi kullanarak grafikleri temsil edebiliriz. Bu eğitimde grafiğin uygulanmasını da tartıştık.
=> Tam C ++ Öğreticiler listesini Keşfetmek İçin Buraya Bakın.
Önerilen Kaynaklar
- Python Gelişmiş Liste Eğitimi (Liste Sırala, Ters Çevir, Dizin, Kopyala, Birleştir, Topla)
- Python Listesi - Öğeler Oluşturun, Erişin, Dilimleyin, Ekleyin veya Silin
- Yaygın Kablosuz Yönlendirici Markaları İçin Varsayılan Yönlendirici IP Adresi Listesi
- Çarpıcı Çizgi Grafikleri Oluşturmak İçin En İyi 12 Çizgi Grafik Oluşturucu Aracı (2021 SIRALAMALAR)
- En İyi Yönlendirici Modelleri İçin Varsayılan Yönlendirici Oturum Açma Parolası (2021 Listesi)
- Resimli C ++ 'da Bağlantılı Liste Veri Yapısı
- Çizim ile C ++ 'da Dairesel Bağlantılı Liste Veri Yapısı
- Çizimle C ++ 'da Çift Bağlantılı Liste Veri Yapısı
