Tarjan algoritması, yönlendirilmiş graflarda güçlü bağlantılı bileşenleri (GBB) tespit etmek amacıyla geliştirilmiş bir graf algoritmasıdır. Algoritmanın amacı, bir grafı alt bileşenlerine ayırarak her bileşen içinde çift yönlü erişim imkânı bulunan düğümleri tanımlamaktır. Güçlü bağlantılı bir bileşen, herhangi iki düğüm arasında karşılıklı bir yolun mevcut olduğu alt graflardır.

Temel Çalışma Prensibi

Tarjan algoritması, derinlik öncelikli arama (DFS) yaklaşımına dayanmaktadır. Her düğüm, keşfedildiği sırada benzersiz bir indeks numarası alır ve bu indeksle ilişkili bir düşük bağlantı değeri hesaplanır. Düşük bağlantı değeri, bir düğümün DFS ağacında kendi alt ağacı içinde ulaşabileceği en düşük indeksli düğümü gösterir. Algoritma, keşif sırasında bir yığın kullanarak geçici olarak düğümleri saklar ve güçlü bir bağlantılı bileşen tamamlandığında ilgili düğümleri yığından çıkararak bileşeni tanımlar.

Kullanılan Veri Yapıları

Tarjan algoritması, aşağıdaki veri yapılarını kullanır:

Komşuluk Listesi: Grafın temsil edilmesi için.
Yığın: DFS sırasında geçici olarak düğümlerin tutulması için.
İndeks ve Düşük Bağlantı Değeri Dizileri: Düğüm keşif zamanlarını ve düşük bağlantı değerlerini izlemek için.
onStack Dizisi: Bir düğümün hâlen yığında olup olmadığını takip etmek için.
sccs Listesi: Bulunan güçlü bağlantılı bileşenlerin saklanması için.

Zaman ve Alan Karmaşıklığı

Tarjan algoritmasının zaman karmaşıklığı O(V + E) şeklindedir. Burada V, düğüm sayısını, E ise kenar sayısını ifade eder. Bu karmaşıklık, algoritmanın her düğümü ve kenarı yalnızca bir kez işlemesinden kaynaklanır. Alan karmaşıklığı ise O(V) düzeyindedir ve bu, kullanılan ek veri yapılarına bağlıdır.

Uygulama Alanları

Tarjan algoritması, bilgisayar bilimlerinin çeşitli alanlarında kullanılmaktadır. Öne çıkan kullanım alanları arasında sosyal ağ analizi, derleyici optimizasyonu, web taraması, biyolojik ağ çözümlemeleri, devre tasarımı, bağımlılık çözümlemesi ve ağ güvenilirliği analizi bulunmaktadır.

Örnek Üzerinden Tarjan Algoritması Adım Adım

Kullanılan Grafik

Aşağıdaki yönlendirilmiş grafiği ele alalım:

0 → 1 → 2
↑         ↓
6 ← 5 ← 3 → 4 → 7

Grafın kenar listesi şu şekildedir:

0 → 1
1 → 2
2 → 0
2 → 5
5 → 6
6 → 0
3 → 4
4 → 7
7 → 3

Bu grafikte iki adet güçlü bağlantılı bileşen (GBB) bulunmaktadır:

{0, 1, 2, 5, 6}
{3, 4, 7}

Algoritmanın Adım Adım İşleyişi

1. DFS Başlangıcı: Düğüm 0'dan başlanır.

2. İndeks ve Düşük Bağlantı Değerleri: Her düğüme sırayla bir index atanır. İlk ziyaret edilen düğümün lowlink değeri kendi index değeriyle başlar.

3. Yığın Kullanımı: Ziyaret edilen düğümler yığına alınır.

4. Geri Kenarlar: Ziyaret edilen bir düğüm, yığında daha önce var olan başka bir düğüme ulaşabiliyorsa, lowlink değeri güncellenir.

5. Bileşen Tespiti: Eğer bir düğümün lowlink değeri kendi index değerine eşitse, bu düğüm bir bileşenin kök düğümüdür. Yığından düğümler çıkarılarak bir güçlü bağlantılı bileşen oluşturulur.

Tarjan Algoritmasının Python Koduyla Uygulaması

def tarjans_algorithm(graph):
    index = 0
    index_map = {}
    lowlink_map = {}
    stack = []
    on_stack = set()
    sccs = []
    def strongconnect(v):
        nonlocal index
        index_map[v] = index
        lowlink_map[v] = index
        index += 1
        stack.append(v)
        on_stack.add(v)
        for w in graph[v]:
            if w not in index_map:
                strongconnect(w)
                lowlink_map[v] = min(lowlink_map[v], lowlink_map[w])
            elif w in on_stack:
                lowlink_map[v] = min(lowlink_map[v], index_map[w])
        if lowlink_map[v] == index_map[v]:
            scc = []
            while True:
                w = stack.pop()
                on_stack.remove(w)
                scc.append(w)
                if w == v:
                    break
            sccs.append(scc)
    for v in graph:
        if v not in index_map:
            strongconnect(v)
    return sccs
# Grafiği tanımlıyoruz
graph = {
    0: [1],
    1: [2],
    2: [0, 5],
    3: [4],
    4: [7],
    5: [6],
    6: [0],
    7: [3]
}
# Algoritmayı çalıştır
sccs = tarjans_algorithm(graph)
print("Güçlü Bağlantılı Bileşenler:", sccs)

Çıktı

Güçlü Bağlantılı Bileşenler: [[6, 5, 2, 1, 0], [7, 4, 3]]

^【1】

Adım Adım Anlatım

Düğüm 0 ziyaret edilir (index=0, lowlink=0), yığına eklenir.
Düğüm 1 ziyaret edilir (index=1, lowlink=1), yığına eklenir.
Düğüm 2 ziyaret edilir (index=2, lowlink=2), yığına eklenir.
2'nin komşusu olan 0 zaten yığında olduğundan, 2'nin lowlink değeri güncellenir: lowlink[2] = 0.
2'nin diğer komşusu 5'e geçilir.
Düğüm 5 ziyaret edilir (index=3, lowlink=3), yığına eklenir.
5'in komşusu 6'ya geçilir.
Düğüm 6 ziyaret edilir (index=4, lowlink=4), yığına eklenir.
6'nın komşusu olan 0 zaten yığında olduğundan, 6'nın lowlink değeri güncellenir: lowlink[6] = 0.
6 için DFS tamamlanır, 5'in lowlink değeri güncellenir: lowlink[5] = 0.
5 için DFS tamamlanır, 2'nin lowlink değeri güncellenir: lowlink[2] = 0.
2 için DFS tamamlanır, 1'in lowlink değeri güncellenir: lowlink[1] = 0.
1 için DFS tamamlanır, 0'ın lowlink değeri güncellenir: lowlink[0] = 0.
0 için DFS tamamlanır, 0'ın lowlink == index olduğu anlaşılır ve {6, 5, 2, 1, 0} yığından çıkarılarak bir GBB oluşturulur.
Düğüm 3 ziyaret edilir (index=5, lowlink=5), yığına eklenir.
3'ün komşusu 4'e geçilir.
Düğüm 4 ziyaret edilir (index=6, lowlink=6), yığına eklenir.
4'ün komşusu 7'ye geçilir.
Düğüm 7 ziyaret edilir (index=7, lowlink=7), yığına eklenir.
7'nin komşusu 3 zaten yığında olduğundan, 7'nin lowlink değeri güncellenir: lowlink[7] = 5.
7 için DFS tamamlanır, 4'ün lowlink değeri güncellenir: lowlink[4] = 5.
4 için DFS tamamlanır, 3'ün lowlink değeri güncellenir: lowlink[3] = 5.
3 için DFS tamamlanır ve {7, 4, 3} yığından çıkarılarak bir diğer GBB oluşturulur.

Tarihçe

Tarjan algoritması, 1972 yılında Amerikalı bilgisayar bilimcisi Robert Tarjan tarafından geliştirilmiştir. Algoritmanın tanıtımı, Tarjan’ın "Depth-first search and linear graph algorithms" başlıklı çalışmasıyla yapılmıştır. Tarjan ayrıca splay ağaçları ve Fibonacci yığınları gibi başka veri yapılarının geliştirilmesine de katkıda bulunmuştur.

Benzer Algoritmalar ve Varyasyonlar

Tarjan algoritmasına alternatif olarak Kosaraju algoritması da güçlü bağlantılı bileşenleri bulmak için kullanılmaktadır. Kosaraju algoritması iki ayrı DFS geçişi ve grafın ters çevrilmesini gerektirirken, Tarjan algoritması tek bir DFS geçişi ile sonuca ulaşır. Ayrıca, paralel işlemler için geliştirilmiş varyantlar da literatürde yer almaktadır.

Tarjan Algoritması