ALGORITMA FILTER-KRUSKAL SEBAGAI SALAH SATU SOLUSI MINIMUM SPANNING TREE; THE FILTER-KRUSKAL ALGORITHM MINIMUM SPANNING TREE SOLUTION

Zakky, Ahmad, Adhitya Ronnie Effendie

2016 | Skripsi | FMIPA

Filter-Kruskal is a simple modification of Kruskal’s Algorithm that avoids sorting edges that are obviously not in the MST. For arbitrary graph with random edge wights Filter-Kruskal runs in time O(m + n log n log m n ), i.e. in linear time for not too sprase graphs. Experiments indicate that the algorithm has very good practical performance over the entire range of edge densities.

Kata Kunci : N