--- title: Tarjan Algoritması slug: tarjan-algoritmasi-d5872 url: /detay/tarjan-algoritmasi-d5872 type: blog language: Türkçe entity: primary: Tarjan Algoritması type: blog disambiguation: Tarjan Algoritması: Yönlendirilmiş graflarda güçlü bağlantılı bileşenleri bulmak için etkili bir algoritma. O(V+E) karmaşıklığı. categories: - name: Bilişim Ve İletişim Teknolojileri slug: bilisim-ve-iletisim-teknolojileri url: /kategori/bilisim-ve-iletisim-teknolojileri - name: Yazılım Ve Yapay Zekâ slug: yazilim-ve-yapay-zeka url: /kategori/yazilim-ve-yapay-zeka tags: - Tarjan Algoritması - Tarjans Algorithm author: Sinan Turan created_at: 2025-04-27T00:28:41.662102+03:00 updated_at: 2025-04-27T18:11:43.388980+03:00 --- # Tarjan Algoritması ## Article Content Tarjan algoritması, yönlendirilmiş graflarda güçlü bağlantılı bileşenleri (GBB) tespit etmek amacıyla geliştirilmiş bir [graf algoritmasıdır](/tr/detay/algoritma-nedir-744353/llms.txt). [Algoritmanın](/tr/detay/algoritma-6/llms.txt) 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](/tr/detay/yigin-stack-veri-yapisi-564ce/llms.txt) 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](/tr/detay/sosyal-ag-3/llms.txt), 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: #### **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ı** #### **Çıktı** [^1]  #### **Adım Adım Anlatım** 1. **Düğüm 0** ziyaret edilir (***index=0, lowlink=0***), yığına eklenir. 2. **Düğüm 1** ziyaret edilir (***index=1, lowlink=1***), yığına eklenir. 3. **Düğüm 2** ziyaret edilir (***index=2, lowlink=2***), yığına eklenir. 4. 2'nin komşusu olan 0 zaten yığında olduğundan, 2'nin ***lowlink ***değeri güncellenir: ***lowlink[2] = 0***. 5. 2'nin diğer komşusu 5'e geçilir. 6. **Düğüm 5** ziyaret edilir (***index=3, lowlink=3***), yığına eklenir. 7. 5'in komşusu 6'ya geçilir. 8. **Düğüm 6** ziyaret edilir (***index=4, lowlink=4***), yığına eklenir. 9. 6'nın komşusu olan 0 zaten yığında olduğundan, 6'nın ***lowlink ***değeri güncellenir: ***lowlink[6] = 0***. 10. 6 için DFS tamamlanır, 5'in ***lowlink ***değeri güncellenir: ***lowlink[5] = 0***. 11. 5 için DFS tamamlanır, 2'nin ***lowlink*** değeri güncellenir: lowlink[2] = 0. 12. 2 için DFS tamamlanır, 1'in ***lowlink ***değeri güncellenir: lowlink[1] = 0. 13. 1 için DFS tamamlanır, 0'ın ***lowlink*** değeri güncellenir: lowlink[0] = 0. 14. 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. 15. **Düğüm 3** ziyaret edilir (***index=5, lowlink=5)***, yığına eklenir. 16. 3'ün komşusu 4'e geçilir. 17. **Düğüm 4** ziyaret edilir (***index=6, lowlink=6***), yığına eklenir. 18. 4'ün komşusu 7'ye geçilir. 19. **Düğüm 7** ziyaret edilir (***index=7, lowlink=7***), yığına eklenir. 20. 7'nin komşusu 3 zaten yığında olduğundan, 7'nin ***lowlink ***değeri güncellenir: ***lowlink[7] = 5***. 21. 7 için DFS tamamlanır, 4'ün ***lowlink ***değeri güncellenir: ***lowlink[4] = 5***. 22. 4 için DFS tamamlanır, 3'ün ***lowlink*** değeri güncellenir: ***lowlink[3] = 5***. 23. 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](/tr/detay/veri-yapilari/llms.txt) geliştirilmesine de katkıda bulunmuştur. ### **Benzer Algoritmalar ve Varyasyonlar** [Tarjan algoritmasına](/tr/detay/tarjans-algorithm-7a859/llms.txt) alternatif olarak [Kosaraju algoritması](/tr/detay/kruskals-algorithm-72f6f/llms.txt) 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. ## Academic Sources and References 1. Algocademy. "Tarjan's Algorithm: Unraveling Strongly Connected Components in Graphs." Erişim 26 Nisan 2025. https://algocademy.com/blog/tarjans-algorithm-unraveling-strongly-connected-components-in-graphs/.GeeksforGeeks. "Strongly Connected Components." Erişim 26 Nisan 2025. https://www.geeksforgeeks.org/strongly-connected-components/.GeeksforGeeks. "Tarjan’s Algorithm in C." Erişim 26 Nisan 2025. https://www.geeksforgeeks.org/tarjans-algorithm-in-c/.GeeksforGeeks. "Tarjan’s Algorithm in Python." Erişim 26 Nisan 2025. https://www.geeksforgeeks.org/tarjans-algorithm-in-python/.Tutorialspoint. "Tarjan’s Algorithm in Graph Theory." Erişim 26 Nisan 2025. https://www.tutorialspoint.com/graph\_theory/graph\_theory\_tarjans\_algorithm.htm.Youcademy. "Tarjan’s Strongly Connected Components Algorithm." Erişim 26 Nisan 2025. https://youcademy.org/tarjans-scc-algorithm/. ## Citations [^1]: Bileşen içindeki düğümlerin sırası yığından çıkarılma sırasına göre olabilir. ## Related Articles - [SOLID Prensipleri](//detay/solid-prensipleri/llms.txt) - [Yapısal Tasarım Kalıpları](//detay/yapisal-tasarim-kaliplari-e9388/llms.txt) - [Yüksek Seviye Programlama Dilleri](//detay/yuksek-seviye-programlama-dilleri-16c59/llms.txt) - [God Object ](//detay/god-object-65275/llms.txt)