Ebben a cikkben a Kruskal-algoritmusról fogunk beszélni. Itt látni fogjuk a Kruskal-algoritmus bonyolultságát, működését, példáját és megvalósítását is.
Mielőtt azonban közvetlenül az algoritmus felé haladnánk, először meg kell értenünk az olyan alapvető kifejezéseket, mint a feszítőfa és a minimális feszítőfa.
Feszítőfának - A feszítőfa egy irányítatlan összefüggő gráf részgráfja.
Minimális feszülő fa - Minimális feszítőfa az a feszítőfa, amelyben az él súlyainak összege minimális. A feszítőfa súlya a feszítőfa éleihez adott súlyok összege.
Most pedig kezdjük a fő témával.
Kruskal algoritmusa egy összefüggő súlyozott gráf minimális feszítőfájának megkeresésére szolgál. Az algoritmus fő célja, hogy megtalálja az élek azon részhalmazát, amellyel a gráf minden csúcsát bejárhatjuk. Azt a mohó megközelítést követi, amely minden szakaszban megtalálja az optimális megoldást ahelyett, hogy a globális optimumra összpontosítana.
Hogyan működik a Kruskal-algoritmus?
Kruskal algoritmusában a legkisebb súlyú élekből indulunk ki, és addig adjuk össze az éleket, amíg el nem érjük a célt. A Kruskal-algoritmus megvalósításának lépései a következők:
- Először is rendezze szét az összes élt a kis súlytól a magasig.
- Most vegye a legkisebb súlyú élt, és adja hozzá a feszítőfához. Ha a hozzáadandó él ciklust hoz létre, akkor utasítsa el az élt.
- Addig folytassuk az élek hozzáadását, amíg el nem érjük az összes csúcsot, és létrejön egy minimális fedőfa.
A Kruskal-algoritmus alkalmazásai a következők:
- A Kruskal-algoritmus felhasználható az elektromos vezetékek városok közötti elrendezésére.
- LAN-kapcsolatok lefektetésére használható.
Példa a Kruskal-algoritmusra
Most pedig nézzük meg a Kruskal-algoritmus működését egy példa segítségével. Egy példa segítségével könnyebb lesz megérteni Kruskal algoritmusát.
Tegyük fel, hogy egy súlyozott gráf -
A fenti grafikon éleinek súlyát az alábbi táblázat tartalmazza -
| Él | AB | AC | HIRDETÉS | DE | időszámításunk előtt | CD | NAK,-NEK |
| Súly | 1 | 7 | 10 | 5 | 3 | 4 | 2 |
Most rendezze a fent megadott éleket súlyuk növekvő sorrendjében.
| Él | AB | NAK,-NEK | időszámításunk előtt | CD | DE | AC | HIRDETÉS |
| Súly | 1 | 2 | 3 | 4 | 5 | 7 | 10 |
Most kezdjük el megépíteni a minimális feszítőfát.
python generál uuid
1. lépés - Először is tegyük hozzá a szélét AB súllyal 1 az MST-hez.
2. lépés - Adja hozzá a szélét NAK,-NEK súllyal 2 az MST-hez, mivel nem az hozza létre a ciklust.
3. lépés - Adja hozzá a szélét időszámításunk előtt súllyal 3 az MST-hez, mivel nem hoz létre ciklust vagy hurkot.
4. lépés - Most válassza ki a szélét CD súllyal 4 az MST-hez, mivel nem ez alkotja a ciklust.
5. lépés - Ezután válassza ki a szélét DE súllyal 5. Ennek az élnek a bevonása létrehozza a ciklust, ezért dobja el.
6. lépés - Válassza ki a szélét AC súllyal 7. Ennek az élnek a bevonása létrehozza a ciklust, ezért dobja el.
7. lépés - Válassza ki a szélét HIRDETÉS súllyal 10. Ennek az élnek a bevonása a ciklust is létrehozza, ezért dobja el.
Tehát az adott súlyozott gráfból a Kruskal-algoritmus segítségével kapott végső minimális feszítőfa:
Az MST költsége = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.
Most a fenti fa éleinek száma egyenlő a csúcsok számával mínusz 1. Tehát az algoritmus itt megáll.
Algoritmus
Step 1: Create a forest F in such a way that every vertex of the graph is a separate tree. Step 2: Create a set E that contains all the edges of the graph. Step 3: Repeat Steps 4 and 5 while E is NOT EMPTY and F is not spanning Step 4: Remove an edge from E with minimum weight Step 5: IF the edge obtained in Step 4 connects two different trees, then add it to the forest F (for combining two trees into one tree). ELSE Discard the edge Step 6: END
Kruskal algoritmusának összetettsége
Most pedig nézzük meg a Kruskal-algoritmus időbeli összetettségét.
A Kruskal-algoritmus időbonyolultsága O(E logE) vagy O(V logV), ahol E a sz. élek, és V a sz. csúcsok közül.
Kruskal-algoritmus megvalósítása
Most pedig lássuk a kruskal algoritmus megvalósítását.
Program: Írjon programot a kruskal algoritmus megvalósítására C++ nyelven.
#include #include using namespace std; const int MAX = 1e4 + 5; int id[MAX], nodes, edges; pair <long long, pair> p[MAX]; void init() { for(int i = 0;i <max;++i) id[i]="i;" } int root(int x) { while(id[x] !="x)" id[x]="id[id[x]];" x="id[x];" return x; void union1(int x, y) p="root(x);" q="root(y);" id[p]="id[q];" long kruskal(pair<long long, pair> p[]) { int x, y; long long cost, minimumCost = 0; for(int i = 0;i <edges;++i) { x="p[i].second.first;" y="p[i].second.second;" cost="p[i].first;" if(root(x) !="root(y))" minimumcost +="cost;" union1(x, y); } return minimumcost; int main() x, y; long weight, cost, init(); cout <> nodes >> edges; for(int i = 0;i <edges;++i) { cout<> x >> y >> weight; p[i] = make_pair(weight, make_pair(x, y)); } sort(p, p + edges); minimumCost = kruskal(p); cout <<'minimum cost is '<< minimumcost << endl; return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/85/kruskals-algorithm-6.webp" alt="Kruskal"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'minimum></edges;++i)></edges;++i)></max;++i)></long>