Kruskal’s Algoritması nedir? | Minimum Spanning Tree

Kruskal's Algoritması, bir weighted graph verildiğinde, bu graf'ı içeren en küçük ağırlıklı ağacı (minimum spanning tree) bulmak için kullanılan bir algoritmadır. Bu ağaç, verilen graf'ın düğümlerini ve bazı kenarlarını içerir, ancak döngüler içermez ve tüm düğümleri bağlar.

#algoritmalar #programlama #yazılım

Kruskal'ın Algoritması adım adım şu şekildedir:

1. Tüm kenarları ağırlıklarına göre sırala: İlk adımda, verilen grafın kenarlarını ağırlıklarına göre sıralarsın, böylece en hafif kenarlar en önce gelir.

2. Boş bir ağaç oluştur: Başlangıçta, minimum ağırlıklı ağaç (MST) boş bir ağaçtır.

3. Kenarları eklemeye başla: Sıralanmış kenar listesini ele alın. Her bir kenarı ele aldığınızda şunları yapın:

- Eğer bu kenar, ağacın bir döngü oluşturmasına neden olmazsa (yani, bu kenarın uç düğümleri ağaçta aynı bileşende değilse), o zaman bu kenarı MST'ye ekle.

- Eğer bu kenar, ağacın bir döngü oluştururduysa, o zaman bu kenarı atla.

4. Tüm düğümler ağaçta olduğunda dur: Algoritma, tüm düğümler minimum ağırlıklı ağaçta olduğunda sona erer.

Kruskal's algoritmasının temel fikri, her adımda ağırlıkları küçük olan kenarları eklemektir. Ancak, döngüleri engellemek için yalnızca ağaçta aynı bileşende olmayan kenarları eklersiniz. Bu şekilde, sonunda tüm düğümleri bağlayan en küçük ağırlıklı ağacı elde etmiş olursunuz.

Bu algoritma, genellikle graph teorisi problemlerinde kullanılır, özellikle iletişim ağları, elektrik ağları, ulaşım ağları gibi alanlarda optimal yolların veya bağlantıların bulunmasında kullanılır.

Kaynaklar:

https://en.wikipedia.org/wiki/Kruskal...
https://www.geeksforgeeks.org/kruskal...
https://cp-algorithms.com/graph/mst_k...

Leetcode sorusu:

https://leetcode.com/problems/min-cos...

***

🤖 LEETCODE ►    • Leetcode  
💚 HACKERRANK ►    • Hackerrank  
👌 HACKERRANK- 30 DAYS OF CODE ►    • Hackerrank - 30 Days of Code  
🎁 C# YENİLİKLERİ ►    • C#  
💜 SIFIRDAN C# PROGRAMLAMA EĞİTİMİ ►    • Sıfırdan C# Programlama Eğitim Seti  
🔆 C# SHORTS ►    • Shorts  
💛 CODECADEMY EĞİTİMLERİ ►    • Codecademy  
🎨 .NET YENİLİKLERİ ►    • .NET  
⭐ .NET MAUI VİDEOLARI ►    • .NET MAUI  
🎖️ VISUAL STUDIO VİDEOLARI ►    • Visual Studio  
🎉 BENCHMARKDOTNET VİDEOLARI ►    • BenchmarkDotNet  
✨ ALGORİTMA VİDEOLARI ►    • Algoritma  

🐦 Twitter'dan takip edin ►   / sonergonul  
💜 Twitch'ten takip edin ►   / sonergonul  
💚 Discord kanalımız ►   / discord  
💖 Quora'dan takip edin ► https://www.quora.com/profile/Soner-G...
💛 Instagram'dan takip edin ►   / sonergonul  
✨ Tiktok'tan takip edin ►  / soner_gonul  

💪 KATIL:    / soner gönül