Greedy algoritmalar …, Böl. 2: Bağlı Bileşen Etiketleme

Önceki bölümde Kruskal Algoritması ile “Minimum Spanning Tree” bulurken;
1. Çözümü oluşturan küçük bileşenleri en iyiden en kötüye sıralamıştık.
2. Çözümü oluşturmak üzere birleştirmeye başlamıştık.

Bu yazıda birleştirme kuralı üzerinde duracağım:
En iyi parçaları alıp en az ağırlıklı ağacı oluştururken, birden fazla küçük ağaçlar(fidanlar 🙂 ) oluşacaktır.

Bu oluşumu takip edebilmek için, graftan aldığımız her yeni kenarı, var olan ağaçlar içinde ait olduğu ağacın etiketiyle etiketlemeliyiz. Yani o ağaca birleştirmeliyiz.

Başlangıçta, ilk aldığımız ağaç, herhangi bir ağaca ait olmayacağı için buna bir etiket verilir. Mesela 1. Ağaç denir. Daha sonra farklı bir ağaç oluştuğunda ona sırayla yeni numaralar verilerek farklı ağaç olduğu etiketlenir. Burada farklı bir ağaçtan kastettiğim şey, yeni eklenen kenarın var olan bir ağacın devamı olmayıp, ayrık olmasıdır.

Oluşan farklı ağaçları birleştirirken, graftan yeni alınan kenarın(ağacın);

  • var olan bir ağacın devamı,
  • iki farklı ağacı birleştirdiği,

kriterlerine bakarız.
Bu durumlar oluştuğunda, ağaçlar birleştirilir. Yani, farklı iki etiket, tek etiketle ifade edilir.

Bu etiketleme işleminin mantığı, aynı özellikte olan ve birbirine bağlı bileşenlerin bir grupta ifade edilmesidir. Bu işleme “Bağlı Bileşen Etiketleme” (Connected Component Labeling) adı verilir.

Bu yöntemin uygulanmasıyla döngü oluşmadan “min. spanning tree” oluşması sağlanır.

Sonuç:

“Greedy” algoritmaları bir anlamda “Recursive” algoritmalara benzetebiliriz.
Bir durma koşulu olması kaydıyla, temel bir işlem tekrar eder.

-- The End --

Copyright © 2010 – Taha Yavuz Bodur

Advertisements

Leave a comment

Filed under Algoritmalar

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s