Dalam tutorial ini, Anda akan mempelajari bagaimana Algoritma Kruskal bekerja. Juga, Anda akan menemukan contoh kerja dari Algoritma Kruskal di C, C ++, Java dan Python.
Algoritma Kruskal adalah algoritma pohon rentang minimum yang mengambil grafik sebagai input dan menemukan subset dari tepi grafik itu yang
- membentuk pohon yang mencakup setiap simpul
- memiliki jumlah bobot minimum di antara semua pohon yang dapat dibentuk dari grafik
Bagaimana algoritma Kruskal bekerja
Ini termasuk dalam kelas algoritma yang disebut algoritma serakah yang menemukan optimal lokal dengan harapan menemukan optimal global.
Kami mulai dari tepi dengan bobot terendah dan terus menambahkan tepi sampai kami mencapai tujuan kami.
Langkah-langkah implementasi algoritma Kruskal adalah sebagai berikut:
- Sortir semua tepi dari yang berbobot rendah hingga tinggi
- Ambil tepi dengan bobot terendah dan tambahkan ke pohon rentang. Jika menambahkan tepi menciptakan siklus, maka tolak tepi ini.
- Terus tambahkan tepi sampai kita mencapai semua simpul.
Contoh algoritma Kruskal
Mulailah dengan grafik berbobot 
Pilih tepi dengan bobot paling kecil, jika ada lebih dari 1, pilih siapa pun 
Pilih tepi terpendek berikutnya dan tambahkan 
Pilih tepi terpendek berikutnya yang tidak membuat siklus dan tambahkan 
Pilih tepi terpendek berikutnya yang tidak membuat siklus dan menambahkannya 
Ulangi sampai Anda memiliki pohon rentang
Pseudocode Algoritma Kruskal
Algoritme pohon rentang minimum berputar di sekitar memeriksa apakah menambahkan tepi menciptakan loop atau tidak.
Cara paling umum untuk mengetahuinya adalah algoritma yang disebut Union FInd. Algoritme Union-Find membagi simpul menjadi beberapa kluster dan memungkinkan kita untuk memeriksa apakah dua simpul milik klaster yang sama atau tidak dan karenanya memutuskan apakah menambahkan sebuah sisi menciptakan sebuah siklus.
KRUSKAL(G): A = ∅ For each vertex v ∈ G.V: MAKE-SET(v) For each edge (u, v) ∈ G.E ordered by increasing order by weight(u, v): if FIND-SET(u) ≠ FIND-SET(v): A = A ∪ ((u, v)) UNION(u, v) return A
Contoh Python, Java dan C / C ++
Python Java C ++ # Kruskal's algorithm in Python class Graph: def __init__(self, vertices): self.V = vertices self.graph = () def add_edge(self, u, v, w): self.graph.append((u, v, w)) # Search function def find(self, parent, i): if parent(i) == i: return i return self.find(parent, parent(i)) def apply_union(self, parent, rank, x, y): xroot = self.find(parent, x) yroot = self.find(parent, y) if rank(xroot) rank(yroot): parent(yroot) = xroot else: parent(yroot) = xroot rank(xroot) += 1 # Applying Kruskal algorithm def kruskal_algo(self): result = () i, e = 0, 0 self.graph = sorted(self.graph, key=lambda item: item(2)) parent = () rank = () for node in range(self.V): parent.append(node) rank.append(0) while e < self.V - 1: u, v, w = self.graph(i) i = i + 1 x = self.find(parent, u) y = self.find(parent, v) if x != y: e = e + 1 result.append((u, v, w)) self.apply_union(parent, rank, x, y) for u, v, weight in result: print("%d - %d: %d" % (u, v, weight)) g = Graph(6) g.add_edge(0, 1, 4) g.add_edge(0, 2, 4) g.add_edge(1, 2, 2) g.add_edge(1, 0, 4) g.add_edge(2, 0, 4) g.add_edge(2, 1, 2) g.add_edge(2, 3, 3) g.add_edge(2, 5, 2) g.add_edge(2, 4, 4) g.add_edge(3, 2, 3) g.add_edge(3, 4, 3) g.add_edge(4, 2, 4) g.add_edge(4, 3, 3) g.add_edge(5, 2, 2) g.add_edge(5, 4, 3) g.kruskal_algo()
// Kruskal's algorithm in Java import java.util.*; class Graph ( class Edge implements Comparable ( int src, dest, weight; public int compareTo(Edge compareEdge) ( return this.weight - compareEdge.weight; ) ); // Union class subset ( int parent, rank; ); int vertices, edges; Edge edge(); // Graph creation Graph(int v, int e) ( vertices = v; edges = e; edge = new Edge(edges); for (int i = 0; i < e; ++i) edge(i) = new Edge(); ) int find(subset subsets(), int i) ( if (subsets(i).parent != i) subsets(i).parent = find(subsets, subsets(i).parent); return subsets(i).parent; ) void Union(subset subsets(), int x, int y) ( int xroot = find(subsets, x); int yroot = find(subsets, y); if (subsets(xroot).rank subsets(yroot).rank) subsets(yroot).parent = xroot; else ( subsets(yroot).parent = xroot; subsets(xroot).rank++; ) ) // Applying Krushkal Algorithm void KruskalAlgo() ( Edge result() = new Edge(vertices); int e = 0; int i = 0; for (i = 0; i < vertices; ++i) result(i) = new Edge(); // Sorting the edges Arrays.sort(edge); subset subsets() = new subset(vertices); for (i = 0; i < vertices; ++i) subsets(i) = new subset(); for (int v = 0; v < vertices; ++v) ( subsets(v).parent = v; subsets(v).rank = 0; ) i = 0; while (e < vertices - 1) ( Edge next_edge = new Edge(); next_edge = edge(i++); int x = find(subsets, next_edge.src); int y = find(subsets, next_edge.dest); if (x != y) ( result(e++) = next_edge; Union(subsets, x, y); ) ) for (i = 0; i < e; ++i) System.out.println(result(i).src + " - " + result(i).dest + ": " + result(i).weight); ) public static void main(String() args) ( int vertices = 6; // Number of vertices int edges = 8; // Number of edges Graph G = new Graph(vertices, edges); G.edge(0).src = 0; G.edge(0).dest = 1; G.edge(0).weight = 4; G.edge(1).src = 0; G.edge(1).dest = 2; G.edge(1).weight = 4; G.edge(2).src = 1; G.edge(2).dest = 2; G.edge(2).weight = 2; G.edge(3).src = 2; G.edge(3).dest = 3; G.edge(3).weight = 3; G.edge(4).src = 2; G.edge(4).dest = 5; G.edge(4).weight = 2; G.edge(5).src = 2; G.edge(5).dest = 4; G.edge(5).weight = 4; G.edge(6).src = 3; G.edge(6).dest = 4; G.edge(6).weight = 3; G.edge(7).src = 5; G.edge(7).dest = 4; G.edge(7).weight = 3; G.KruskalAlgo(); ) )
// Kruskal's algorithm in C #include #define MAX 30 typedef struct edge ( int u, v, w; ) edge; typedef struct edge_list ( edge data(MAX); int n; ) edge_list; edge_list elist; int Graph(MAX)(MAX), n; edge_list spanlist; void kruskalAlgo(); int find(int belongs(), int vertexno); void applyUnion(int belongs(), int c1, int c2); void sort(); void print(); // Applying Krushkal Algo void kruskalAlgo() ( int belongs(MAX), i, j, cno1, cno2; elist.n = 0; for (i = 1; i < n; i++) for (j = 0; j < i; j++) ( if (Graph(i)(j) != 0) ( elist.data(elist.n).u = i; elist.data(elist.n).v = j; elist.data(elist.n).w = Graph(i)(j); elist.n++; ) ) sort(); for (i = 0; i < n; i++) belongs(i) = i; spanlist.n = 0; for (i = 0; i < elist.n; i++) ( cno1 = find(belongs, elist.data(i).u); cno2 = find(belongs, elist.data(i).v); if (cno1 != cno2) ( spanlist.data(spanlist.n) = elist.data(i); spanlist.n = spanlist.n + 1; applyUnion(belongs, cno1, cno2); ) ) ) int find(int belongs(), int vertexno) ( return (belongs(vertexno)); ) void applyUnion(int belongs(), int c1, int c2) ( int i; for (i = 0; i < n; i++) if (belongs(i) == c2) belongs(i) = c1; ) // Sorting algo void sort() ( int i, j; edge temp; for (i = 1; i < elist.n; i++) for (j = 0; j elist.data(j + 1).w) ( temp = elist.data(j); elist.data(j) = elist.data(j + 1); elist.data(j + 1) = temp; ) ) // Printing the result void print() ( int i, cost = 0; for (i = 0; i < spanlist.n; i++) ( printf("%d - %d : %d", spanlist.data(i).u, spanlist.data(i).v, spanlist.data(i).w); cost = cost + spanlist.data(i).w; ) printf("Spanning tree cost: %d", cost); ) int main() ( int i, j, total_cost; n = 6; Graph(0)(0) = 0; Graph(0)(1) = 4; Graph(0)(2) = 4; Graph(0)(3) = 0; Graph(0)(4) = 0; Graph(0)(5) = 0; Graph(0)(6) = 0; Graph(1)(0) = 4; Graph(1)(1) = 0; Graph(1)(2) = 2; Graph(1)(3) = 0; Graph(1)(4) = 0; Graph(1)(5) = 0; Graph(1)(6) = 0; Graph(2)(0) = 4; Graph(2)(1) = 2; Graph(2)(2) = 0; Graph(2)(3) = 3; Graph(2)(4) = 4; Graph(2)(5) = 0; Graph(2)(6) = 0; Graph(3)(0) = 0; Graph(3)(1) = 0; Graph(3)(2) = 3; Graph(3)(3) = 0; Graph(3)(4) = 3; Graph(3)(5) = 0; Graph(3)(6) = 0; Graph(4)(0) = 0; Graph(4)(1) = 0; Graph(4)(2) = 4; Graph(4)(3) = 3; Graph(4)(4) = 0; Graph(4)(5) = 0; Graph(4)(6) = 0; Graph(5)(0) = 0; Graph(5)(1) = 0; Graph(5)(2) = 2; Graph(5)(3) = 0; Graph(5)(4) = 3; Graph(5)(5) = 0; Graph(5)(6) = 0; kruskalAlgo(); print(); )
// Kruskal's algorithm in C++ #include #include #include using namespace std; #define edge pair class Graph ( private: vector
G; // graph vector
T; // mst int *parent; int V; // number of vertices/nodes in graph public: Graph(int V); void AddWeightedEdge(int u, int v, int w); int find_set(int i); void union_set(int u, int v); void kruskal(); void print(); ); Graph::Graph(int V) ( parent = new int(V); //i 0 1 2 3 4 5 //parent(i) 0 1 2 3 4 5 for (int i = 0; i < V; i++) parent(i) = i; G.clear(); T.clear(); ) void Graph::AddWeightedEdge(int u, int v, int w) ( G.push_back(make_pair(w, edge(u, v))); ) int Graph::find_set(int i) ( // If i is the parent of itself if (i == parent(i)) return i; else // Else if i is not the parent of itself // Then i is not the representative of his set, // so we recursively call Find on its parent return find_set(parent(i)); ) void Graph::union_set(int u, int v) ( parent(u) = parent(v); ) void Graph::kruskal() ( int i, uRep, vRep; sort(G.begin(), G.end()); // increasing weight for (i = 0; i < G.size(); i++) ( uRep = find_set(G(i).second.first); vRep = find_set(G(i).second.second); if (uRep != vRep) ( T.push_back(G(i)); // add to tree union_set(uRep, vRep); ) ) ) void Graph::print() ( cout << "Edge :" << " Weight" << endl; for (int i = 0; i < T.size(); i++) ( cout << T(i).second.first << " - " << T(i).second.second << " : " << T(i).first; cout << endl; ) ) int main() ( Graph g(6); g.AddWeightedEdge(0, 1, 4); g.AddWeightedEdge(0, 2, 4); g.AddWeightedEdge(1, 2, 2); g.AddWeightedEdge(1, 0, 4); g.AddWeightedEdge(2, 0, 4); g.AddWeightedEdge(2, 1, 2); g.AddWeightedEdge(2, 3, 3); g.AddWeightedEdge(2, 5, 2); g.AddWeightedEdge(2, 4, 4); g.AddWeightedEdge(3, 2, 3); g.AddWeightedEdge(3, 4, 3); g.AddWeightedEdge(4, 2, 4); g.AddWeightedEdge(4, 3, 3); g.AddWeightedEdge(5, 2, 2); g.AddWeightedEdge(5, 4, 3); g.kruskal(); g.print(); return 0; )
Algoritma Kruskal vs Prim
Algoritme Prim adalah algoritme pohon rentang minimum populer lainnya yang menggunakan logika berbeda untuk menemukan MST grafik. Alih-alih memulai dari tepi, algoritme Prim dimulai dari simpul dan terus menambahkan tepi dengan bobot terendah yang tidak ada di pohon, sampai semua simpul telah tertutup.
Kompleksitas Algoritma Kruskal
Kompleksitas waktu Algoritma Kruskal adalah: O (E log E).
Aplikasi Algoritma Kruskal
- Untuk tata letak kabel listrik
- Di jaringan komputer (koneksi LAN)
