hkucuk

Borůvka'nın Algoritması: Minimum Kapsayan Ağaçları Bulmak İçin Etkili Bir Yöntem

20 Mart 2024 • ☕️ 5 dk okuma • 🏷 bilgisayar, yazılım, algoritma, graf

Yazar tarafından şu dillere çevrildi: English


Borůvka’nın algoritması, minimum kapsayan ağaçları bulmak için kullanılan etkili bir graf algoritmasıdır. Graf teorisinde önemli bir yere sahip olan bu algoritma, bir graf içindeki en küçük ağırlıklı kenarları seçerek ve bu kenarları birleştirerek minimum kapsayan ağaçları oluşturur. Temel prensibi graf içindeki her bir düğümü kapsayan ağaçlara ayırmak ve ardından bu ağaçları birleştirerek birbirine bağlamaktır.

Algoritmanın işleyişi oldukça basittir ancak etkilidir. İlk adımda, her bir düğüm bir minimum kapsayan ağacın kökü olarak kabul edilir. Daha sonra graf içindeki en düşük ağırlıklı kenarlar seçilir ve bu kenarlar kullanılarak minimum kapsayan ağaçlar oluşturulur. Bu süreç graf içindeki minimum kapsayan ağaç sayısı azaldıkça tekrarlanır.

Borůvka’nın algoritmasının verimliliği grafın büyüklüğüne bağlı olarak değişkenlik gösterebilir. Özellikle büyük ve yoğun graf yapıları için daha hızlı sonuçlar elde edilebilirken, daha küçük ve seyrek graf yapıları için daha uzun sürebilir. Ancak paralel hesaplama olanaklarından faydalanılarak algoritmanın performansı artırılabilir.

Bu algoritmanın avantajlarından biri paralel hesaplama için uygun olmasıdır. Adımların bağımsız olarak yürütülebilmesi, paralel işlemcilerde verimliliği artırabilir. Ayrıca, minimum kapsayan ağaçları bulma problemlerinde geniş bir uygulama alanı bulunmaktadır. İletişim ağlarının oluşturulması, elektrik şebekelerinin planlanması gibi alanlarda minimum kapsayan ağaçlar önemli bir rol oynamaktadır.

Borůvka’nın algoritması, minimum kapsayan ağaçları bulma problemlerinde etkili bir çözüm sunar. Graf teorisindeki önemli bir araç olarak kabul edilir ve çeşitli uygulama alanlarında kullanılmaktadır. Ancak grafın büyüklüğüne ve yapısına bağlı olarak algoritmanın verimliliği değişebilir.

Algoritmanın Çalışma Prensibi

Borůvka’nın algoritması, aşağıdaki adımları takip eder:

  1. Başlangıç Adımı: Köklerin Belirlenmesi

    • Algoritma başlangıcında, her düğüm kendine ait bir minimum kapsayan ağacın kökü olarak kabul edilir.
    • Grafın her bir düğümü, kendi kendine bir ağacın kökü olarak işaretlenir.

  2. Kenar Seçme Adımı: En Küçük Ağırlıklı Kenarların Belirlenmesi

    • Graf içindeki her ağacın kökünden dışa doğru giden kenarlardan en küçük ağırlıklı olanları belirlenir.
    • Her ağacın kökünden, o ağaca bağlı olan kenarlardan en küçük ağırlığa sahip olanı seçilir.

  3. Kenarları Birleştirme Adımı: Ağaçların Birleştirilmesi

    • Belirlenen en küçük ağırlıklı kenarlar kullanılarak minimum kapsayan ağaçlar birleştirilir.
    • Seçilen her kenar, iki farklı ağacı birleştirerek daha büyük bir ağaç oluşturur.

  4. Tekrarlama Adımı: Yeniden Değerlendirme

    • Eğer graf içinde birden fazla minimum kapsayan ağaç varsa, bu adımlar tekrarlanır.
    • Yeniden değerlendirme adımında, her bir ağaç kökünden en küçük ağırlıklı kenarlar seçilerek ve ağaçlar birleştirilerek işlem devam ettirilir.

  5. Bitiş Adımı: Minimum Kapsayan Ağaçların Oluşumu

    • Graf içinde sadece bir minimum kapsayan ağaç kaldığında veya belirlenen bir kriter karşılandığında algoritma sonlanır.
    • Algoritma sonucunda, graf içindeki en küçük ağırlıklı kenarlar kullanılarak minimum kapsayan ağaçlar oluşturulur.
    • Bu adımlar sonucunda graf içindeki minimum kapsayan ağaçlar tamamlanmış olur.

Algoritma Karmaşıklığı

Borůvka’nın algoritmasının karmaşıklığı, genellikle O(E log V) olarak ifade edilir, burada E, kenar sayısı ve V, düğüm sayısıdır. Ancak, grafın yoğunluğuna ve yapısal özelliklerine bağlı olarak bu karmaşıklık değişebilir.

Önemli Bilgiler

  1. Borůvka’nın algoritması, paralel hesaplama için uygundur çünkü adımlar bağımsız olarak yürütülebilir.
  2. Bu algoritma, ağaç tabanlı ağ yapısı gerektiren problemlerde yaygın olarak kullanılır.
  3. Borůvka’nın algoritması, belirli koşullar altında diğer minimum kapsayan ağaç algoritmalarından daha hızlı olabilir.

Borůvka’nın algoritması, minimum kapsayan ağaçları bulmak için etkili bir yöntem olmasının yanı sıra, graf teorisine olan katkılarıyla da bilinir. Karmaşıklığı ve performans avantajları, çeşitli problemlerde kullanılmasını sağlar.

GoLang’de Borůvka’nın Algoritması uygulaması:

package main

import (
	"fmt"
	"sort"
)

type Edge struct {
	src, dest, weight int
}

type Graph struct {
	V, E int
	edge []Edge
}

func createGraph(V, E int) *Graph {
	graph := &Graph{V: V, E: E}
	graph.edge = make([]Edge, E)
	return graph
}

func find(parent []int, i int) int {
	if parent[i] == -1 {
		return i
	}
	return find(parent, parent[i])
}

func union(parent []int, x, y int) {
	xset := find(parent, x)
	yset := find(parent, y)
	parent[xset] = yset
}

func boruvkaMST(graph *Graph) {
	V, E := graph.V, graph.E
	parent := make([]int, V)
	for i := range parent {
		parent[i] = -1
	}
	cheapest := make([]int, V)
	for i := range cheapest {
		cheapest[i] = -1
	}

	numTrees := V
	minimumCost := 0
	for numTrees > 1 {
		for i := range cheapest {
			cheapest[i] = -1
		}

		for i := 0; i < E; i++ {
			set1 := find(parent, graph.edge[i].src)
			set2 := find(parent, graph.edge[i].dest)

			if set1 != set2 {
				if cheapest[set1] == -1 || graph.edge[cheapest[set1]].weight > graph.edge[i].weight {
					cheapest[set1] = i
				}
				if cheapest[set2] == -1 || graph.edge[cheapest[set2]].weight > graph.edge[i].weight {
					cheapest[set2] = i
				}
			}
		}

		for i := 0; i < V; i++ {
			if cheapest[i] != -1 {
				set1 := find(parent, graph.edge[cheapest[i]].src)
				set2 := find(parent, graph.edge[cheapest[i]].dest)

				if set1 != set2 {
					minimumCost += graph.edge[cheapest[i]].weight
					fmt.Printf("Edge %d-%d included in MST\n", graph.edge[cheapest[i]].src, graph.edge[cheapest[i]].dest)
					union(parent, set1, set2)
					numTrees--
				}
			}
		}
	}
	fmt.Printf("Minimum Cost Spanning Tree: %d\n", minimumCost)
}

func main() {
	V, E := 4, 5
	graph := createGraph(V, E)

	graph.edge[0] = Edge{src: 0, dest: 1, weight: 10}
	graph.edge[1] = Edge{src: 0, dest: 2, weight: 6}
	graph.edge[2] = Edge{src: 0, dest: 3, weight: 5}
	graph.edge[3] = Edge{src: 1, dest: 3, weight: 15}
	graph.edge[4] = Edge{src: 2, dest: 3, weight: 4}

	boruvkaMST(graph)
}

Program çalıştırıldığında çıktısı aşağıdaki gibi olacaktır.

Edge 0-3 included in MST
Edge 0-1 included in MST
Edge 2-3 included in MST
Minimum Cost Spanning Tree: 19

Programın çalışır haline şuradan erişilebilir.

Kaynaklar