Graph Algoritmaları: BFS, DFS ve Dijkstra’yı Graph Lab ile Görün

Graph algoritmaları; sosyal ağlardan navigasyona, dependency analysis’ten network tasarımına kadar çok geniş bir problem ailesini çözer. Zorluk, yalnızca çok sayıda algoritma bulunması değildir. Aynı graph’ın farklı representation’ları, farklı problem hedefleri ve farklı edge koşulları hangi yöntemin doğru olduğunu belirler.

Websoftik Academy Graph Algorithms Lab, graph görünümü, adjacency matrix, adjacency list ve edge list’i senkronize eder. BFS’den Bellman–Ford’a dokuz deterministik algoritma trace’i; frontier, visited set, safe edge, relaxation ve partial result state’lerini adım adım açıklar.

Bir graph G=(V,E), vertex kümesi ve bu vertex’ler arasındaki edge’lerden oluşur. Directed veya undirected, weighted veya unweighted, connected veya disconnected olabilir. Küçük bir model farkı doğru algoritmayı tamamen değiştirir: negatif edge bulunan graph’ta Dijkstra kullanmak gibi.

İkinci zorluk algoritmanın aynı anda birkaç state tutmasıdır. BFS queue’yu, DFS recursion stack’i, Dijkstra tentative distance’ları, Prim cut’ı takip eder. Yalnızca vertex ziyaret sırasına bakmak bu kararların nedenini gizler.

Graph Algorithms Lab, foundations, representations, traversal, applications, minimum spanning tree, shortest path ve exam practice alanlarını bağlantılı bir rota olarak sunar.

Trace paneli her adımda phase, açıklama, “neden?”, aktif vertex ve edge’ler, pseudocode satırı, state ve partial result verir. Playback hızı değişse bile input ve tie-breaking aynı kaldığında trace deterministiktir; bu sayede kendi tahmininizle Lab sonucunu güvenilir biçimde karşılaştırabilirsiniz.

Lab’de bir edge eklediğinizde dört görünüm aynı anda değişir. Böylece bunların dört ayrı graph değil, aynı abstract yapının farklı physical representation’ı olduğunu görürsünüz.

BFS source’a olan hop distance’a göre katman katman ilerler ve queue kullanır. Unweighted graph’ta source’tan her vertex’e minimum edge sayılı yolu bulur. Parent ilişkisi tutulduğunda hedefe path reconstruction yapılabilir.

DFS bir branch boyunca mümkün olduğunca derine iner, sonra geri döner. Recursion veya explicit stack ile uygulanabilir. Cycle detection, topological ordering, SCC ve low-link algoritmalarının temelidir. Recursive call davranışını ayrıca Recursion Lab rehberinde inceleyebilirsiniz.

Topological order, directed acyclic graph’taki her u→v edge’i için u vertex’ini v’den önce yerleştirir. Ders ön koşulları, build dependency’leri ve task scheduling bu modele uyar. Graph’ta directed cycle varsa geçerli bir topological order yoktur.

Lab, DFS finish order ile cycle condition’ı birlikte gösterir. Böylece ortaya çıkan listeyi ezberlemek yerine neden yalnızca DAG üzerinde geçerli olduğunu edge yönleri üzerinden doğrularsınız.

Directed graph’ta strongly connected component içindeki her vertex diğerine erişebilir. Kosaraju algoritması DFS finish order ve transposed graph üzerinde ikinci traversal ile bu component’leri ayırır.

Undirected graph’ta bir edge çıkarıldığında component sayısı artıyorsa bu edge bridge; bir vertex çıkarıldığında artıyorsa vertex articulation point’tir. Discovery time ve low-link değerleri, bir subtree’nin ancestor’a alternatif bağlantısı olup olmadığını kodlar. Lab bu sayıların güncellenmesini aktif DFS tree üzerinde gösterir.

Connected, undirected, weighted graph’ın bütün vertex’lerini cycle olmadan ve minimum toplam edge ağırlığıyla bağlayan yapı minimum spanning tree’dir. MST, source’tan hedefe shortest path bulmaz; bütün ağı en düşük toplam bağlantı maliyetiyle kapsar. Bu iki problem sıkça karıştırılır.

Prim tek bir tree büyütür. Tree içindeki vertex’lerle dışarıdaki vertex’ler arasındaki cut’ı geçen en güvenli edge’i seçer. Heap tabanlı uygulama adjacency list ile O(E log V), matrix/min-array yaklaşımı Θ(V²) çalışabilir.

Kruskal bütün edge’leri ağırlığa göre sıralar ve cycle oluşturmayanları seçer. Edge sorting O(E log E) maliyetindedir; component kontrolünü Union-Find neredeyse sabit amortized maliyetle yönetir. Disjoint Set mantığı için Union-Find rehberimizi kullanabilirsiniz.

Önce input koşulunu, sonra gereken garantiyi seçmek gerekir. Lab’in selection guide’ı algoritma adını problem cümlesindeki “unweighted”, “negative edge” ve “negative cycle” gibi sinyallerle eşleştirir.

Dijkstra source distance’ını 0, diğerlerini infinity ile başlatır. En küçük tentative distance’a sahip vertex settle edilir ve outgoing edge’leri relax edilir. dist[u] + w(u,v) < dist[v] ise distance ve parent güncellenir.

Nonnegative edge koşulu, settle edilen distance’ın daha sonra iyileşmeyeceği garantisini verir. Lab distance table, priority frontier ve seçilen edge’i senkronize eder; hedefe ulaşıldığında parent chain üzerinden path’i yeniden kurar. Heap sürümü O((V+E) log V), matrix sürümü Θ(V²) maliyetindedir.

Bellman–Ford bütün edge’leri en fazla V-1 tur relax eder. Negatif edge’lerle doğru shortest path bulabilir ve ek bir turda hâlâ iyileşme varsa reachable negative cycle tespit eder. Worst-case maliyeti O(VE), değişiklik olmayan turda early exit yapılırsa O(kE) olabilir.

Dijkstra’dan yavaş olması onu “kötü” yapmaz; çözdüğü input sınıfı daha geniştir. Lab aynı weighted graph üzerinde iki algoritmanın relaxation ve settle davranışlarını karşılaştırarak trade-off’u açıklar.

BFS ve DFS adjacency list üzerinde O(V+E) çalışırken adjacency matrix üzerinde her vertex için bütün olası komşular tarandığından Θ(V²) olur. Dense graph’ta bu fark küçük olabilir; sparse graph’ta matrix gereksiz tarama ve alan üretir.

Complexity yalnızca algoritmanın değil algoritma + representation çiftinin özelliğidir. Büyüme sınıflarını grafiklerle karşılaştırmak için Complexity Lab rehberine geçebilirsiniz.

Önce trace’i durdurup sıradaki vertex, edge veya distance update’i tahmin edin. Ardından tek adım ilerleyip “Why?” açıklamasını kendi gerekçenizle karşılaştırın. Sadece animasyonu izlemek yerine frontier ve partial result’ı kâğıt üzerinde yeniden üretmek, sınavda gerekli olan execution skill’i geliştirir.

Graph Algorithms Lab’i açın ve dokuz algoritmayı aynı trace diliyle karşılaştırın. Tüm interaktif öğrenme araçlarına Academy Lab sayfasından ulaşabilirsiniz.