ZAFER CÖMERT

Öğretim Üyesi

VERİ YAPILARILARI VE ALGORİTMALAR

Graph
Giriş
1. Çizge veri yapısı
2. Yönlü ve yönsüz çizgeler
3. Ağırlıklı çizgeler
4. Çizgeler veri yapısı örnekleri
5. Çizgelere ilişkin kavramlar
Çizge
(Graph)

𝐺 ∶= (V, 𝐸 ሻ

Vertex Edge
Düğümler Kenarlar
Çizge
(Graph)

• 𝑉 = {𝐴, 𝐵, 𝐶, 𝐷}

• 𝐸 = {(𝐴, 𝐵ሻ, (𝐴, 𝐷ሻ, (𝐶, 𝐷ሻ}

Çizge
(Graph)

𝐺 ∶= ({𝐴, 𝐵, 𝐶, 𝐷} , {(𝐴, 𝐵ሻ, (𝐴, 𝐷ሻ, (𝐶, 𝐷ሻ}ሻ

Çizge
(Graph)

• Düğümler (vertex) ve kenarları kullanarak

bağlantıları temsil etmenin soyut bir
yoludur.

• Düğümler 1 den 𝑛’e kadar etiketlenir.

• 𝑚 adet kenar bazı düğümlere bağlanır.

• Kenarlar tek yönlü (one-directional, directed) ya
da çift yönlü (bidirectional) olabilir.

• Düğümler ve kenarlar bazı yardımcı bilgiler

içerebilir.
Yönlü Kenar
(Directed Edge)

• Bir çift sıralı düğüm (u,v)

• İlk düğüm u, orijini temsil eder.
• İkinci düğüm v, varış noktasını temsil eder.
• Örnek: tek-yön trafik
Yönsüz Kenar
(Undirected Edge)

• Bir çift sırasız düğüm (u,v)

• Örnek: Demir yolu
Yönlü Graf
(Directed graph)

• Tüm kenarlar yönlüdür.

• Örnek: Yönlendirme ağı
(Root network)
Yönlü çevrimsiz graf
(Directed Acyclic Graph (DAG))

• Bir yönlü çevrimsiz graf (DAG, directed acyclic graph) çevrim

içermeyen yönlü bir graftır.
Yönsüz Graf
(Directed graph)

• Tüm kenarlar yönsüzdür.

• Örnek: Uçuş ağı (flight
network)
Ağırlıklı Graf
(Weighted Graph)

• Ağırlıklı graflarda iki düğümü birleştiren kenarların belirli bir

ağırlığı vardır. Bu ağırlık noktalar arasındaki ilişkiyi tanımlar.
Bazen bu ağırlıklar maliyet olarak da ifade edilebilir.
Ağırlıklı ve Yönlü Graf
(Weighted DiGraph)

• Ağırlıklı graflarda iki düğümü birleştiren kenarların belirli bir

ağırlığı vardır. Bu ağırlık noktalar arasındaki ilişkiyi tanımlar.
Bazen bu ağırlıklar maliyet olarak da ifade edilebilir. Kenar aynı
zamanda yön bilgisine de sahipse bu çizge ağırlıklı ve yönlü
olarak ifade edilir.
Çizge
• Bir çizgede çevrim yok ise ağaç (tree) olarak ifade edilir. Bir ağaç
çevrimsel olmayan bağlı bir graftır (acyclic connected graph).
Çizge
• Bir düğümü kendine bağlayan kenara öz-çevrim (self-loop)
denir.
Döngü
(self-loop)

• Bir yol başladığı düğümden yine başladığı düğüme gidecek şekilde

de tanımlanabilir. Bu çoğu zaman bir döngü (self-loop) olarak
adlandırılır ve maliyeti genellikle 0 (sıfır) olarak tanımlanır.
Çizge
• İki kenar aynı düğümleri bağlıyor ise paraleldir.
Çevrim
(cycle)

Çevrim • Çevirim yolun başladığı düğümde bitmesidir.

• D>C>E>D
• G>F>E>D>G • Çevrim sırasında tekrar eden bir düğüm ya da
kenar yok ise ilgili ifade basit çevrim (simple
• C>D>E>C cycle) olarak ifade edilir.
Yol
(Path)

• Graf üzerinde bir yol tanımı, ilk düğümden başlamak üzere; yol
üzerindeki son düğüme ulaşıncaya kadar olan maliyet şeklide
tanımlanabilir.
• Yol üzerinde tekrar eden düğüm yok ise bu basit yol (simple path)
şeklide ifade edilir.
Düğüm derecesi
(Degree)

• Düğüm derecesi, düğümün sahip olduğu kenar sayısını ifade

etmek üzere kullanılır. Yönlü graflar için bu derece indeg (giren
kenar sayısı) ve outdeg (çıkan kenar sayısı) şeklinde ifade
edilebilir.
Güçlü Bağlı Çizge
(Strongly Connected Graph)

• Yönsüz bir graf, eğer bir düğümden tüm düğümlere ulaşacak

şekilde bir yola sahipse güçlü bağlı/bağlantılı graf (strongly
connected graph) olarak ifade edilir.
Güçlü Bağlı Çizge
(Strongly Connected Graph)

• Bir graf güçlü bağlantılı değilse bu zayıf bağlı (weakly

connected graph) olarak ifade edilir.
Tam Çizge
(Complete Graph)

• Her bir düğüm bir diğerine komşu olmalıdır. Tek bir adımda bir
düğümden bir başka düğüme gidilebilmelidir.
• 𝑛 düğüm için 𝑛(𝑛 − 1ሻ/2 kenar bulunur.
Bileşen
(Component)

• Bağlı olmayan graflardaki her bir ada, ya da ayrık küme, bir

bileşen (component) olarak ifade edilir.
Düzenli Çizge
(Regular Graph)

• Bağlı graf yapısındadır.

• Bütün düğümlerin derecesi aynıdır.
İki parçalı çizge
(Bipartite graph)

• Ayrık iki küme vardır ve

bağlantılar, kenar bu iki
küme arasında kurulur.

F
Tam iki parçalı çizge
(Complete bipartite graph)

• İki parçalı graf içinde bir

düğüm; diğer gruptaki her bir
düğüme doğrudan bağlı
olmalıdır.
Kapsama Ağacı
(Spanning tree)

 Bütün düğümleri içeren alt graftır. Her bir düğümün en fazla iki bağlantısı vardır.
Çizge Temsili
Graph Representation
• Bitişiklik matrisi (Adjacency matrix)
• Bitişiklik listesi (Adjacency list)
• Bitişiklik kümesi (Adjacency set)
Çizgelerin Depolanması
• 𝑉 adet düğüm ve 𝐸 adet kenarın depolanması ihtiyacı:
• Düğümler dizi de depolanabilir.
• Kenarlar başka bir şekilde (örneğin komşuluk matrisi ya da komşuluk
listesi gibi) saklanmalıdır.

• Gerçekleştirilmek istenen işlevler

• Belirli bir düğüm ile ilgili tüm kenarları alma
• İki düğümün doğrudan bağlı olup olmadığını test etme

• Komşuluk/Bitişiklik matrisi ya da listesi kenarları depolamak

için kullanılabilir.
Komşuluk Matrisi
(Adjancency Matrix)

• Bağlantı bilgilerini depolanın kolay bir yoludur.

• İki düğümün bir birine doğrudan bağlı olup/olmama durumu test
etmenin maliyeti: 𝑂(1ሻ

• n x n matrisi
• 𝑎𝑖𝑗 = 1 eğer 𝑖 düğümünden 𝑗 düğümüne bağlantı varsa
• 𝑎𝑖𝑗 = 0 diğer durumda

• Θ(𝑛2 ሻ hafıza kullanır.

• Yalnızca n birkaç binden az olduğunda kullanın.
• Ve graf yoğun olduğunda
Komşuluk Matrisi
(Adjacency Matrix)

• Grafların komşu liste gösterimi ve komşu matris gösterimi

olmak üzere temelde iki farklı gösterim şekli bulunmaktadır.

• Komşuluk matrisinde G grafi 𝑁 𝑥 𝑁 tane elemandan oluşan

bir komşuluk matrisi ile ifade edilir. Matrisi 𝑛𝑖𝑗 eğer i
düğümünden j düğümüne bir kenar var ise 1 değerini alır; aksi
durumda 0 değeri ile ifade edilir.
Komşuluk Matrisi
(Adjacency Matrix)
Komşuluk Matrisi
(Adjacency Matrix)

• 𝑉𝑥𝑉 boyunda bir matris ile temsil edilir.

• Matris genellikle boolean veri tipindedir.

• Yönsüz graflarda simetriktir.

• Yönlü graflarda sadece bağlı olan

düğümler dikkate alınarak oluşturulur.
Ağırlık Matrisi
(Weighted Matrix)
Komşu Liste
(Adjancency List)

• Her düğüm kendisinden çıkan kenarların bir listesine sahiptir.

• Belirli bir düğüme ilişkin olayda kenarlar üzerinde iteratif işlevleri
yürütmek kolaydır.
• Listenin uzunluğu değişken olabilir.
• Bellek kullanımı (Θ(𝑛 + 𝑚ሻ)
Komşu Liste
(Adjancency List)

C
Komşuluk Listesinin Uygulanması
• Çözüm 1: Bağlı listeler
• Çok fazla bellek kullanımı/bellek zaman ek yükü
• Dinamik ayrılmış bellek veya işaretçiler kullanmak kötü

• Çözüm 2: Vektrölerin Dizileri

• Kodlama daha kolay, kötü hafıza sorunu yok
• Ancak çok yavaş.

• Çözüm 3: Diziler
• Toplam kenar sayısının bilinmesi varsayımı
• Çok hızlı ve bellek-verimli
Dizilerin bir uygulaması
Çizge Uygulamaları
Applications of Graphs
Çizge Uygulamaları (Applications)
• En kısa yol problemleri
• Taşıma ağlarının modellenmesi (Karayolu ağı, Uçuş ağı)
• Bilgisayar ağlarının modellenmesi (LAN, Internet, Web)
• Eşleşme problemleri
• Gezgin satıcı problemleri
• Çizge renklendirme problemleri
• Veri tabanları: Entity Relationship diyagramları
• Elektronik devre elemanları arasındaki ilişkinin temsil edilmesi
• Rota planlama
• Tedarik zincirleri
Çizge problemlerinin dört sınıfı
Çizge
(Graph)
Ağ Çizgesi
(Network Graph)
Sosyal Ağ Çizgesi
(Social Network Graph)
Veri Yapıları ve Algoritmalar
ZAFER CÖMERT
Öğretim Üyesi