Grafik Veri Yapısı Eğitimi

Hesaplamada, bir grafik, bağlantılar ile birbirine bağlanan bir dizi düğümdür. Bir ağaç ve bir grafik arasındaki temel fark, bir ağacın bir kök düğüme sahip olması, bir grafiğin ise birden fazla kök düğüme sahip olmasıdır. Buraya gelmeden önce zaten ağaç veri yapısı hakkında temel bilgilere sahip olmalısınız, çünkü oradaki kavramlar burada çok az açıklama ile veya hiç açıklama olmadan kullanılacaktır. Bu bilgiye sahip değilseniz, https://linuxhint bağlantısındaki Yeni Başlayanlar için Ağaç Veri Yapısı Eğitimi başlıklı öğreticiyi okuyun.com/tree_data_structure_tutorial_beginners/.

Grafikteki bir düğüme tepe noktası denir (çoğul - tepe noktaları). Bazen hala bir düğüm olarak adlandırılır; bir nokta olarak da adlandırılabilir. Grafikteki bir bağlantıya kenar denir. Bazen hala bağlantı olarak adlandırılır; çizgi olarak da adlandırılabilir.

Birçok Özellikli Grafik

Bu şekil, birçok özelliği olan bir grafiği göstermektedir:

Daireler (diskler) köşelerdir. Herhangi bir düz çizgi veya eğri çizgi veya döngü bir kenardır.

Grafiğin Özellikleri

tepe noktası

Köşe bir nesnedir. Bir ev olabilir; bir kişi olabilir; soyut bir isim olabilir; aklınıza gelebilecek herhangi bir nesne olabilir.

kenar

Kenar, iki köşe arasındaki bağlantıdır (ilişki); bağlantı soyut olabilir.

döngü

Döngü, bir köşeyi kendisine bağlayan bir kenardır.

Ok Kenarı

İki kişiyi düşünün: John ve Peter. John, Peter'a 100 $ borç verirse ve John ve Peter köşelerse, o zaman borç verme kenarı Peter'ı işaret edecektir. Her iki ortak da Peter'ın John'a borçlu olduğunu unutursa ve Peter John'a 100 dolar borç verirse, aynı kenarın diğer ucunda bir ok ucu John'u işaret edecektir. Peter John'a 100 dolar değil de 75 dolar borç verseydi, o zaman farklı bir avantaj Peter'ı John'a bağlardı. Bu ikinci kenarın ok ucu John'u gösterecek. İkinci durumda, her biri birer ok ucu olan ve zıt yönleri gösteren iki kenar vardır.

Bir kenarın işaret ettiği tepe noktası, o kenar için bir baş tepe noktasıdır. Bir kenarın çıktığı tepe noktası, bir kuyruk tepe noktasıdır.

olay

Kenar iki köşeyi birbirine bağlar. Kenarın her iki tepe noktasında da olay olduğu söylenir. Kenarın bir ok ucuna sahip olması gerekmez. İki köşe, kenarın uç noktaları olarak bilinir. Bir tepe noktasının herhangi bir kenara ait olmadığı bir grafiğe sahip olmak mümkündür, ancak bu eğitimde dikkate alınmayacaktır.

Yönsüz Grafik

Kenar bir ok olabilir veya olamaz. Hiçbir kenarın ok olmadığı bir grafik, yönsüz bir grafiktir. Kenar, düz bir çizgi, bir eğri veya bir döngü ile temsil edilebilir.

Yönlendirilmiş grafik

Her kenarın bir ok (yön) olduğu bir grafik, yönlendirilmiş bir grafiktir. Bir ok kenarı, ok uçlu düz bir çizgi veya ok uçlu bir eğri veya ok uçlu bir döngü ile temsil edilebilir.

Yönsüz bir grafiğin kenarında bir yönün olmaması, yönsüz grafiğin her bir kenarının çift yönlü olduğu anlamına gelir.

Bir Köşe Derecesi

Bir tepe noktasına gelen kenarların sayısı, tepe noktasının derecesidir. Bir döngünün bir tepe noktasında iki insidansı vardır, bu nedenle bir döngü iki kez sayılır.

Bir Grafiğin Sırası

Grafiğin sırası, grafikteki köşe sayısıdır.

çoklu grafik

Çoklu grafik, bazı köşe çiftleri için birden fazla kenarın olduğu bir grafiktir. Yönsüz bir çoklu grafik, kenarların yönü olmadığı (oklar olmadığı) bir grafiktir. Yönlendirilmiş çoklu grafik, her kenarın bir ok olduğu ve birden fazla oku olan köşe çiftleri için, bir köşe bu okların kuyruğu ve diğer köşe aynı okların başıdır. Aşağıdaki şema, yönlendirilmemiş bir çoklu grafiği göstermektedir:

Birden fazla kenar (i.e. çoklu kenarlar) bir çift köşe için paralel kenarlar olarak da adlandırılır.

titreme

Bir titreme, döngülere izin veren bir çoklu grafiktir (bir veya daha fazla döngü). Bazı çoklu grafikler döngülere izin vermez.

Basit Grafik

Basit bir grafik, iki köşe çiftinin birden fazla kenarı olmadığı bir grafiktir. Basit bir grafikte döngülere izin verilmez.

Boş Grafik

Boş bir grafik, köşeleri ve dolayısıyla kenarları olmayan bir grafiktir.

Karışık Grafik

Karışık bir grafik, bazı kenarların ok olduğu ve diğerlerinin olmadığı bir grafiktir; başka bir deyişle: bazı kenarların yönleri vardır ve diğerleri yönlendirilmemiştir.

Ağırlıklı Grafik

Her bir kenara ağırlık olarak bilinen bir sayının atandığı bir grafiğe sahip olmak mümkündür. Bazı kenarlar aynı sayıya sahiptir, ancak sayılar genellikle farklıdır. Böyle bir grafiğe ağırlıklı grafik denir. Belirli bir grafiğin sayıları, soruna bağlı olarak uzunlukları veya maliyetleri (fiyatları) veya bir tür büyüklüğü temsil edebilir.

Derece ve Derece

Kelime, derece ve derece, yalnızca yönlendirilmiş bir grafiğe uygulanabilir. Grafik bir çoklu grafik olabilir veya olmayabilir. Grafiğin döngüleri olabilir veya olmayabilir.

Bir tepe noktasına bağlı ok başlarının sayısı, o tepe noktasının derecesidir. Tek bir ok ucu olan bir okun bir baş ucu ve bir kuyruk ucu vardır. Bir tepe noktasına bağlı kuyrukların sayısı, o tepe noktasının derecesidir.

Not: Köşe çifti için, birden çok kenarın zıt yönlerde olduğu, birden çok kenarı olan bir grafik bu öğreticide ele alınmamıştır.

Bir Grafiğin Yazılım Temsili

Bir grafik, diyagramda çizildiği şekilde yazılımda temsil edilebilir. Bir grafik, yazılımda matematiksel bir matris (iki boyutlu dizi) ile de gösterilebilir. Bu matrislerden birine komşuluk matrisi denir.

komşuluk matrisi

Bir komşuluk matrisi bir kare matristir. Satırların başlıkları, artan sırada yazılmış tüm köşelerdir. Sütunların başlıkları, artan sırada yazılmış, hala aynı köşelerdir. Bir matrisin satırlarının veya sütunlarının sayılması, dizilerde olduğu gibi sıfırdan değil, 1'den başlar. Bir matriste bir eleman tanımlanırken, sütun numarasından önce satır numarası yazılır.

Yönlendirilmemiş bir grafik için, komşuluk matrisindeki her giriş (eleman), karşılık gelen iki köşeyi birleştiren kenarların sayısıdır. Bir döngü iki kez sayılmalıdır. Yönlendirilmiş bir grafik için, bitişiklik matrisindeki her giriş, ya bir satır tepe noktasından ayrılan ve karşılık gelen sütun tepe noktasına giren kenarların sayısıdır ya da bir sütun tepe noktasından ayrılan ve karşılık gelen satır tepe noktasına giren kenarların sayısıdır. Seçim programcının seçimidir. Bu durumda (her iki durumda da), bir döngü yine de bir kez sayılmalıdır.

Not: Grafik bir diyagramdır, başlı başına bir veri yapısıdır. Bitişik matris aynı zamanda kendi başına bir veri yapısıdır.

Yönsüz Grafik ve Bitişiklik Matrisi

Aşağıdaki diyagramlar, yönlendirilmemiş bir grafiği ve karşılık gelen bitişiklik matrisini göstermektedir:

Bir matrisin baştaki köşegeni, sol üstten sağ alt köşegendir. Yönlendirilmemiş bir matris, baştaki köşegen etrafında simetriktir. A satırı ve C sütunu için matris girişi 1'dir, yani A köşesi ile C köşesini birleştiren bir kenar vardır. C satırı ve B sütunu için matris girişi 3'tür, yani C tepe noktası ile B tepe noktasını birleştiren 3 kenar vardır. Diğer girişler benzer şekilde açıklanmıştır.

Bir satır için girişlerin toplamı, karşılık gelen köşe için kenar sayısını (derece) verir. A satırı için girişlerin toplamı 2'dir, yani 2 kenar A köşesine bağlıdır. B satırı için girişlerin toplamı 6'dır, yani 6 kenar B köşesine bağlıdır. Girişlerin geri kalanı benzer şekilde açıklanmıştır.

Yönlendirilmiş Grafik ve Bitişiklik Matrisi

Aşağıdaki diyagramlar, yönlendirilmiş bir grafiği ve karşılık gelen bitişiklik matrisini göstermektedir:

Yönlendirilmiş bir grafik için komşuluk matrisi, baştaki köşegen hakkında mutlaka simetrik değildir. A satırı ve C sütunu için matris girişi 1'dir, yani bir kenar A köşesinden C köşesine ayrılır. C satırı ve B sütunu için matris girişi 3'tür, yani 3 kenar C tepe noktasından B tepe noktasına ayrılır. Diğer girişler benzer şekilde açıklanmıştır.

Bir sütun için girişlerin toplamı, (sütun) tepe noktasının derecesini verir. Bir satır için girişlerin toplamı, (satır) tepe noktasının derecesini verir. A sütunu için girişlerin toplamı 1'dir, yani bir kenar A köşesine yönlendirilir. B satırı için girişlerin toplamı 2'dir, yani 2 kenar B köşesinden ayrılır. Girişlerin geri kalanı benzer şekilde açıklanmıştır.

Grafik İşlemleri

Grafik gibi bir veri yapısı, bir dizi veri değerinden veya bir dizi nesneden, artı nesneler arasındaki ilişkiden ve nesneler arasındaki işlemlerden (işlevlerden) oluşur. Bir grafikteki ilişkiler kenarlarla gösterilir. Bununla ilgili olarak, bir grafik en azından aşağıdaki işlemleri içermelidir:

bitişik(G, x, y)

G grafik anlamına gelir. Bu işlem, bir kenarın köşe x ile köşe y'yi birbirine bağlayıp bağlamadığını doğrular. Bir matristeki bir girişin değeri ve konumu, bir kenarın (ve tipinin) bağlantısını gösterir.

komşular(G, x)

Bu işlem, x köşesine doğrudan bağlı olan tüm köşelerin bir listesini döndürür. Bir matristeki bir girişin değeri ve konumu, bir kenarın bağlantısını gösterir.

remove_vertex(G, x)

Bu işlem, bir köşe noktası olan x'i bir grafikten kaldırır. Köşenin kenarı yoksa sorun yok. Ancak, köşenin bağlantıları varsa, bağlantılar (kenarlar) da kaldırılmalıdır. Bir matristeki bir girdinin değeri ve konumu, belirli bir tepe noktasının varlığını gösterir. Bir köşe kaldırılırsa, matrisin yeniden ayarlanması gerekir.

add_vertex(G, x)

Bu, köşe eklemeden bir köşe, x ekler veya kenarları olan ancak kaldırılmış bir köşeyi değiştirir. Bir matristeki bir girdinin değeri ve konumu, belirli bir tepe noktasının varlığını gösterir. Bir köşe eklenirse, matrisin yeniden ayarlanması gerekir.

add_edge(G, x, y)

Bu işlem, kenar orada değilse, x köşesi ile y köşesi arasına yeni bir kenar ekler. Bir matristeki bir girişin değeri ve konumu, belirli bir kenarın varlığını gösterir. Bir kenar eklenirse, matrisin yeniden ayarlanması gerekir.

kaldır_kenar(G, x, y)

Bu işlem, eğer kenar orada olsaydı, x tepe noktası ile y tepe noktası arasındaki kenarı kaldırırdı. Bir matristeki bir girişin değeri ve konumu, belirli bir kenarın varlığını gösterir. Bir kenar kaldırılırsa, matrisin yeniden ayarlanması gerekir.

get_vertex_value(G, x)

Bu işlem, tepe noktasıyla ilişkili v değerini döndürür, x. Bunu başarmak için, köşe etiketleri ve değerleri için bir güç alt kümesine ihtiyacınız var.

set_vertex_value(G, x, v)

Bu işlem, tepe noktasıyla ilişkili değer için yeni bir v değeri verir, x. Bunu başarmak için, köşe etiketleri ve değerleri için bir güç alt kümesine ihtiyacınız var.

Bazı grafikler değerleri kenarlarıyla da ilişkilendirir. Bu tür grafikler aşağıdaki ek işlemlere ihtiyaç duyar:

get_edge_value(G, x, y)

Bu işlem, kenarla ilişkili v değerini döndürür, (x, y). Bunu başarmak için, kenarlar ve değerleri için bir güç alt kümesine ihtiyacınız var.

set_edge_value(G, x, y, v)

Bu işlem, kenarla ilişkili değer için yeni bir v değeri verir, (x, y). Bunu başarmak için, kenarlar ve değerleri için bir güç alt kümesine ihtiyacınız var.

Sonuç

Grafik, kenarlarla bağlantılı bir dizi köşedir. Bir grafik yönlendirilmemiş veya yönlendirilmiş olabilir. Kenarlar yönsüz veya yönlü olabilir. Bir grafikte döngüler olabilir veya olmayabilir. Bundan sonra öğrenmeniz gereken, grafiklerle ilgili küme, güç kümesi ve çoklu kümedir. Bundan sonra, yönlendirilmiş grafik, düzenli grafik, tam grafik, ikili grafik, turnuva grafiği, akış ağı grafiği vb. gibi farklı grafik türlerini öğrenmelisiniz.

Chrys

Yazar hakkında

kasımpatı

İlk İlkeler ve ilgili serilerden matematik entegrasyonunun keşfedicisi. Teknik Eğitimde Yüksek Lisans Derecesi, Elektronik ve Bilgisayar Yazılımı konusunda uzmanlaşmış. Lisans Elektronik. Ayrıca Bilgisayar ve Telekomünikasyon alanında yüksek lisans düzeyinde bilgi ve deneyime sahibim. 20.000 yazar arasında, devarticles'teki en iyi 37. yazardım.com. 10 yılı aşkın süredir bu alanlarda çalışıyorum.

Tüm gönderileri görüntüle