Kruskal ve Prim Arasındaki Fark

Kruskal vs Prim

Bilgisayar biliminde, Prim ve Kruskal algoritmaları, bağlı ağırlıklı yönlendirilmemiş bir grafik için minimum yayılma ağacı bulan açgözlü bir algoritmadır. Yayılan ağaç, grafiğin her düğümü bir ağaç olan bir yolla bağlanacak şekilde bir grafiğin alt grafiğidir. Her bir yayılma ağacının bir ağırlığı vardır ve tüm yayılma ağaçlarının mümkün olan minimum ağırlıkları / maliyeti minimum yayılma ağacıdır (MST).

Prim's Algorithm hk. Daha fazla bilgi

Algoritma 1930'da Çek matematikçisi Vojtěch Jarník ve daha sonra bağımsız olarak 1957'de bilgisayar bilimcisi Robert C. Prim tarafından geliştirildi. 1959'da Edsger Dijkstra tarafından yeniden keşfedildi. Algoritma üç temel adımda ifade edilebilir;

Düğümlere ve her bir kenarın ilgili ağırlığına sahip bağlı grafik göz önüne alındığında,

1. Grafikten gelişigüzel bir düğüm seçin ve T ağacına ekleyin (bu ilk düğüm olacaktır)

2. Ağaçtaki düğümlere bağlı her bir kenarın ağırlıklarını düşünün ve minimum değeri seçin. T ağacının diğer ucundaki kenarı ve düğümü ekleyin ve kenarı grafikten çıkarın. (İki veya daha fazla minimum varsa herhangi birini seçin)

3. Ağaca n-1 kenarlar eklenene kadar 2. adımı tekrarlayın..

Bu yöntemde, ağaç tek bir rasgele düğüm ile başlar ve her döngüde bu düğümden itibaren genişler. Bu nedenle, algoritmanın düzgün çalışması için grafiğin bağlı bir grafik olması gerekir. Prim algoritmasının temel formu O'nun zaman karmaşıklığına sahiptir (V²).

Kruskal's Algorithm hk. Daha fazla bilgi

Joseph Kruskal tarafından geliştirilen algoritma 1956'da Amerikan Matematik Derneği'nin çalışmalarında ortaya çıktı. Kruskal'ın algoritması da üç basit adımda ifade edilebilir..

Her bir kenarın düğümleri ve ilgili ağırlığı olan grafik göz önüne alındığında,

1. Tüm grafiğin en az ağırlığına sahip yayı seçin ve ağaca ekleyin ve grafikten silin.

2. Kalan kısımlardan en az ağırlıklı olan kenarı bir döngü oluşturmayacak şekilde seçin. Kenarı ağaca ekleyin ve grafikten silin. (İki veya daha fazla minimum varsa herhangi birini seçin)

3. 2. adımdaki işlemi tekrarlayın.

Bu yöntemde, algoritma en az ağırlıklı kenarla başlar ve her döngüde her bir kenarı seçmeye devam eder. Bu nedenle, algoritmada grafiğin bağlanması gerekmez. Kruskal'ın algoritmasının zaman karmaşıklığı O (logV)

Kruskal ve Prim Algoritması arasındaki fark nedir?

• Prim'in algoritması bir düğümle başlarken Kruskal'ın algoritması bir kenarla başlar.

• Prim'in algoritmaları bir düğümden diğerine yayılırken, Kruskal'ın algoritması kenarları kenarın konumu son adıma dayanmayacak şekilde seçer.

• Prim algoritmasında, grafik bağlı bir grafik olmalı, Kruskal'lar ise bağlantısı kesilmiş grafiklerde de çalışabilir.

• Prim algoritması O'nun zaman karmaşıklığına sahiptir (V²) ve Kruskal'ın zaman karmaşıklığı O (logV).