Kruskalov algoritam

Sadržaj

Kako djeluje Kruskalov algoritam
Primjer Kruskalovog algoritma
Pseudokod algoritma Kruskal
Primjeri Pythona, Java i C / C ++
Kruskalov vs Primov algoritam
Složenost algoritma Kruskal
Primjene Kruskalovog algoritma

U ovom ćete tutorijalu naučiti kako djeluje Kruskalov algoritam. Također ćete naći radne primjere Kruskalovog algoritma na C, C ++, Javi i Pythonu.

Kruskalov algoritam minimalni je obuhvaćajući algoritam stabla koji uzima graf kao ulaz i pronalazi podskup rubova tog grafa koji

čine drvo koje uključuje svaki vrh
ima najmanji zbroj težina među svim stablima koja se mogu oblikovati iz grafikona

Kako djeluje Kruskalov algoritam

Podpada pod klasu algoritama zvanih pohlepni algoritmi koji pronalaze lokalni optimum u nadi da će pronaći globalni optimum.

Počinjemo od rubova s najmanjom težinom i nastavljamo dodavati rubove dok ne postignemo cilj.

Koraci za implementaciju Kruskalovog algoritma su sljedeći:

Poredajte sve rubove od male težine do veće
Uzmite rub s najmanjom težinom i dodajte ga na rastegnuto stablo. Ako je dodavanjem ruba stvoren ciklus, odbacite ovaj rub.
Nastavite dodavati rubove dok ne dosegnemo sve vrhove.

Primjer Kruskalovog algoritma

Započnite s ponderiranim grafom

Odaberite rub s najmanjom težinom, ako ih je više od 1, odaberite bilo koga

Odaberite sljedeći najkraći rub i dodajte ga

Odaberite sljedeći najkraći rub koji ne stvara ciklus i dodajte ga

Odaberite sljedeći najkraći rub to ne stvara ciklus i dodajte ga.

Ponavljajte dok ne dobijete rastegnuto stablo

Pseudokod algoritma Kruskal

Bilo koji minimalni algoritam obuhvaćajućeg stabla vrti se oko provjere stvara li dodavanje ruba petlju ili ne.

Najčešći način da se to sazna je algoritam nazvan Union FInd. Algoritam Union-Find dijeli vrhove u klastere i omogućuje nam da provjerimo pripadaju li dva vrha istom klasteru ili ne i stoga odlučujemo hoće li dodavanje ruba stvoriti ciklus.

 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

Primjeri Pythona, Java i C / C ++

Python Java C 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; )

Kruskalov vs Primov algoritam

Primov algoritam je još jedan popularan algoritam minimalnog raspona koji koristi drugu logiku za pronalaženje MST-a grafa. Umjesto da započne s ruba, Primov algoritam započinje s vrha i nastavlja dodavati rubove s najmanjom težinom koji nisu u stablu, sve dok nisu pokriveni svi vrhovi.