Graf veri yapısı nedir?

Graf veri yapısı nedir? www.yzokul.com.tr

Şunu soruyorsun: Graf veri yapısı nedir? Kısa yanıt, bir grafın düğümler kümesi ile onları birbirine bağlayan kenarlardan oluştuğudur. İki çizgiyle birleştirilmiş üç nokta hayal et: bu küçük çizim bile bir graftır. Düğümler noktalardır, kenarlar ise aralarındaki çizgilerdir. Bu basit fikir tüm temeldir ve geri kalan her şey bunun üzerine kurulur. 1

Çizgilerle birbirine bağlanmış noktaların basit bir çizimiyle başla. Her nokta bir düğümdür ve her çizgi bir kenardır. Başlamak için daha fazlasına gerek yok: düğümler artı kenarlar bir graf oluşturur. Henüz oklara, sayılara veya etiketlere ihtiyacın yok. Temel yapıyı görmek için sadece noktalar ve çizgiler yeterlidir. Bu, çizebileceğin en basit graftır. 2

Çizimindeki iki parçayı etiketle. Noktalara düğüm denir; bunlara tepe (vertex) de denir. Çizgilere kenar denir. Her graf, hangi düğümlerin var olduğu ve hangi düğüm çiftlerinin bağlı olduğuyla tanımlanır. Düğümler listesini ve kenarlar listesini biliyorsan, tüm grafı bilirsin. İhtiyacın olan tek şey bu iki bilgi parçasıdır. 3

Şehirleri düğüm, aralarındaki yolları kenar olarak hayal et. O zaman bir yol haritası bir grafa dönüşür. Bu tanıdık örnek, grafların gerçek bağlantıları betimlemek için neden yararlı olduğunu gösterir. Bir haritaya bakıp hangi şehirlerin yollarla doğrudan bağlı olduğunu görebilirsin. Graf tam olarak bunu yakalar: hangi yerlerin bağlı, hangilerinin bağlı olmadığını. Yollar kenarlardır, şehirler düğümlerdir. 4

Tek yönlü bir yolu iki yönlü bir yolla karşılaştır. Bir kenarın yönü olabilir ya da olmayabilir. Bir kenar üzerindeki ok, kenarın yönlü olduğunu gösterir: yalnızca okun gösterdiği yönde gidebilirsin. Düz bir çizgi, kenarın yönsüz olduğunu gösterir: her iki yönde de gidebilirsin. Yönlü kenarlar tek yönlü sokakları, yönsüz kenarlar ise iki yönlü sokakları modeller. 5

Bir kenarın, iki şehir arasındaki mesafe gibi bir sayı taşıyabileceğini gör. Bu sayılara ağırlık denir ve bağlantı hakkında bir şeyi betimler. Örneğin, bir yol kenarı 50 kilometre anlamına gelmek üzere 50 sayısını taşıyabilir. Ağırlıklar, bir grafın her bağlantı hakkında ek bilgi saklamasını sağlar. Graf hâlâ düğümler ve kenarlardan oluşur, ama artık kenarların değerleri vardır. 6

İnsanları düğüm, arkadaşlıkları kenar olarak eşle. O zaman bir sosyal ağ bir grafa dönüşür. Aynı noktalar-ve-çizgiler fikrinin kimin kimi tanıdığını betimlediğini görürsün. Her kişi bir düğümdür ve her arkadaşlık iki kişiyi birbirine bağlayan bir kenardır. Bu, grafların yalnızca yollar için olmadığını gösterir; insan ilişkilerini de betimlerler. Yapı aynıdır: düğümler ve kenarlar. 7

Bilgisayarları veya web sayfalarını düğüm, aralarındaki bağlantıları kenar olarak hayal et. İnternet bir graftır. Bu, grafların yalnızca yolları ve arkadaşlıkları değil, teknik ağları da betimlediğini gösterir. Bir bilgisayar başka bir bilgisayara bağlandığında, bu bir kenardır. Bir web sayfası başka bir sayfaya bağlantı verdiğinde, bu da bir kenardır. İnternet, bağlantılardan oluşan devasa bir graftır. 8

Yan yana birkaç küçük grafa bak. Düğümlerin ne kadar farklı biçimlerde bağlanabildiğine dikkat et. Bazı graflar seyrektir: düğüm sayısına göre az kenarları vardır. Diğerleri yoğundur: çok sayıda kenarları vardır. İkisi de geçerli graftır. Bağlantı örüntüsü çok çeşitli olabilir ve grafları bu kadar yararlı kılan da bu çeşitliliktir. 9

Başladığı yere dönen bir döngü boyunca kenarları izle. Bu döngüye çevrim denir. Bir grafın çevrim içermesine izin verilir. Örneğin, A şehrinden B'ye, sonra B'den C'ye, sonra C'den tekrar A'ya gidebilirsin. Bu, üç düğümlü bir çevrimdir. Çevrimler yollar ve arkadaşlıklar gibi gerçek ağlarda yaygındır. 10

Bir ağacı genel bir grafla karşılaştır. Bir ağaç döngü olmadan dallanır: herhangi iki düğüm arasında tam olarak bir yol vardır. Genel bir graf kendi üzerine döngü yapabilir ve birçok yolu olabilir. Ağaçlar, daha kısıtlı özel bir graf türüdür. Her ağaç bir graftır, ama her graf bir ağaç değildir. Bu farkı aklında tut. 11

Hiç kenarı olmayan bir düğüm gör. Bu düğüm yalıtılmıştır. Ayrıca birbirlerine ulaşılabilen bir düğüm grubu gör; bu grup bağlantılıdır. Bir grafın yalnız düğümleri ve ayrı bağlantılı parçaları olabilir. Örneğin, bir sosyal ağda hiç arkadaşı olmayan bir kişi ve birkaç ayrı arkadaş grubu olabilir. İkisine de bir grafta izin verilir. 12

Bir çizginin hiçbir noktaya değmediği bir çizime bak. Bu geçerli bir kenar değildir. Her kenar var olan iki düğümü birbirine bağlamalıdır. Bir kenar tek başına havada duramaz veya hiçbir şeye bağlanamaz. İki ucunda nokta olmayan bir çizgi görürsen, bu bir hatadır. Her kenarın her iki ucunda bir düğüm olduğundan her zaman emin ol. 13

Yönlü bir kenarı izle ve onu ters yönde gidemeyeceğini gör. Bir bağlantının iki yönde de çalıştığını varsaymadan önce, kenarda ok olup olmadığını kontrol et. Varsa, bağlantı yalnızca tek yönlüdür. Örneğin, tek yönlü bir sokak kenarı ters yönde kullanılamaz. Yön önemlidir, bu yüzden her zaman okları ara. 14

Bir çizimde döngü bul ve bunun hâlâ bir graf olduğunu, yalnızca ağaç olmadığını doğrula. Tüm grafların ağaçlar gibi temiz biçimde dallandığını varsayma. Birçok graf çevrim içerir ve bu tamamen normaldir. Çevrim içeren bir graf hâlâ geçerli bir graftır. Bir döngünün varlığı yalnızca onun bir ağaç olmadığı anlamına gelir. 15

Tüm yanıtı gözden geçir: bir graf, kenarlarla birleştirilmiş düğümlerdir. Kenarlar yönlü ya da yönsüz olabilir ve ağırlık denen değerler taşıyabilir. Graflar, ağaçlardan farklı olarak çevrimler ve birçok bağlantı örüntüsü içerebilir. Yollar, arkadaşlıklar ve internet, hepsi birer graftır. Düğümler ve kenarların her grafın iki yapı taşı olduğunu unutma. Graf veri yapısı işte budur. 16