Kruskals algoritme
Sign in to saveminimum spanning forest algorithm that greedily adds edges
In the Vinony graph
Vinony's link graph records 165 inbound references to Kruskals algoritme, and connects out to Bellman–Ford algorithm, Ackermann function and International Standard Book Number.
It is catalogued under topics including Graph algorithms, Greedy algorithms and Spanning tree.
Vinony links it to 30 Wikipedia language editions.
Key facts
- Class
- Minimum spanning tree algorithm
- Data structure
- Graph
- Worst case performance
- O ( | E | log | V | ) {\displaystyle O(|E|\log |V|)}
via Wikipedia infobox
Wikidata facts
- Named after
- Joseph Kruskal
- Image
- MST kruskal en.gif
Show 6 more facts
- Commons category
- Kruskal's algorithm
- Stack Exchange tag
- stackoverflow.com/tags/kruskals-algorithm
- publication date
- 1956-00-00
- discoverer or inventor
- Joseph Kruskal
- computes solution to
- minimum spanning tree
Sources (2)
via Wikidata · CC0
Article · Nederlands
Kruskals algoritme is een algoritme uit de grafentheorie om de minimaal opspannende boom te vinden voor gewogen grafen. Hierbij zoeken we een deelverzameling van bogen die een boom vormen die alle knopen bevat, waarbij daarenboven het totale gewicht minimaal is. Als de graaf niet volledig verbonden is dan zoekt het een minimaal opspannend woud (een minimale overspannende boom voor elke onverbonden deelgraaf). Kruskals algoritme, beschreven in 1956 is een voorbeeld van een . Het algoritme kan als volgt geformuleerd worden (G is de gegeven graaf): "Voer de volgende stap zo vaak uit als mogelijk: Kies uit de bogen van G die nog niet werden gekozen, de kortste boog die geen kring vormt met de bogen die reeds werden gekozen." Met "kortste boog" bedoelt men de boog met het kleinste gewicht. Als er geen kandidaten meer overblijven vormen de geselecteerde bogen de minimaal opspannende boom.
Abstract from DBpedia / Wikipedia · CC BY-SA