Kruskal's algorithm
Kruskal's algorithm finds a minimum spanning forest of an undirected edge-weighted graph. If the graph is connected, it finds a minimum spanning tree. (A minimum spanning tree of a connected graph is a subset of the edges that forms a tree that includes every vertex, where the sum of the weights of all the edges in the tree is minimized. For a disconnected graph, a minimum spanning forest is composed of a minimum spanning tree for each connected component.) It is a greedy algorithm in graph theory as in each step it adds the next lowest-weight edge that will not form a cycle to the minimum spanning forest.
- Comment
- enKruskal's algorithm finds a minimum spanning forest of an undirected edge-weighted graph. If the graph is connected, it finds a minimum spanning tree. (A minimum spanning tree of a connected graph is a subset of the edges that forms a tree that includes every vertex, where the sum of the weights of all the edges in the tree is minimized. For a disconnected graph, a minimum spanning forest is composed of a minimum spanning tree for each connected component.) It is a greedy algorithm in graph theory as in each step it adds the next lowest-weight edge that will not form a cycle to the minimum spanning forest.
- Depiction
- Has abstract
- enKruskal's algorithm finds a minimum spanning forest of an undirected edge-weighted graph. If the graph is connected, it finds a minimum spanning tree. (A minimum spanning tree of a connected graph is a subset of the edges that forms a tree that includes every vertex, where the sum of the weights of all the edges in the tree is minimized. For a disconnected graph, a minimum spanning forest is composed of a minimum spanning tree for each connected component.) It is a greedy algorithm in graph theory as in each step it adds the next lowest-weight edge that will not form a cycle to the minimum spanning forest. This algorithm first appeared in Proceedings of the American Mathematical Society, pp. 48–50 in 1956, and was written by Joseph Kruskal. It was rediscovered by . Other algorithms for this problem include Prim's algorithm, the reverse-delete algorithm, and Borůvka's algorithm.
- Hypernym
- Algorithm
- Is primary topic of
- Kruskal's algorithm
- Label
- enKruskal's algorithm
- Link from a Wikipage to an external page
- gist.github.com/DanilAndreev/e519d77eff91f03f09616c9170db7941
- www.geeksforgeeks.org/kruskals-minimum-spanning-tree-using-stl-in-c/
- meyavuz.wordpress.com/2017/03/11/how-does-kruskals-algorithm-progress/
- github.com/carlschroedl/kruskals-minimum-spanning-tree-algorithm-example-data
- github.com/carlschroedl/gephi-plugins/tree/minimum-spanning-tree-plugin/modules/MinimumSpanningTree
- gephi.org/plugins/%23/plugin/spanning-tree-plugin
- Link from a Wikipage to another Wikipage
- Ackermann function
- Arbitrary
- Big-O notation
- Binary heap
- Binary logarithm
- Borůvka's algorithm
- Category:Articles containing proofs
- Category:Articles with example pseudocode
- Category:Graph algorithms
- Category:Greedy algorithms
- Category:Spanning tree
- Charles E. Leiserson
- Clifford Stein
- Comparison sort
- Connected component (graph theory)
- Connectivity (graph theory)
- Counting sort
- Cycle (graph theory)
- Dijkstra's algorithm
- Disjoint-set data structure
- Edge (graph theory)
- File:Kruskal Algorithm 1.svg
- File:Kruskal Algorithm 2.svg
- File:Kruskal Algorithm 3.svg
- File:Kruskal Algorithm 4.svg
- File:Kruskal Algorithm 5.svg
- File:Kruskal Algorithm 6.svg
- File:KruskalDemo.gif
- Graph theory
- Greedy algorithm
- Greedy geometric spanner
- Introduction to Algorithms
- Joseph Kruskal
- Mathematical induction
- Michael T. Goodrich
- Minimum spanning tree
- Nonempty
- Prim's algorithm
- Proceedings of the American Mathematical Society
- Pseudocode
- Quicksort
- Radix sort
- Reverse-delete algorithm
- Roberto Tamassia
- Ronald L. Rivest
- Single-linkage clustering
- Spanning tree
- Thomas H. Cormen
- Tree (graph theory)
- Vertex (graph theory)
- Weighted graph
- SameAs
- 4xm4o
- Algorisme de Kruskal
- Algorithme de Kruskal
- Algorithmus von Kruskal
- Algoritmo de Kruskal
- Algoritmo de Kruskal
- Algoritmo di Kruskal
- Algoritmul lui Kruskal
- Algorytm Kruskala
- Kruskal's algorithm
- Kruskal's algorithm
- Kruskal-algoritmus
- Kruskalov algoritmus
- Kruskals algoritm
- Kruskals algoritme
- Kruskalův algoritmus
- m.0f2gx
- Q797860
- Thuật toán Kruskal
- Алгоритм Краскала
- Алгоритм Крускала
- Крускалов алгоритам
- Крускалын алгоритм
- Կրուսկալի ալգորիթմ
- האלגוריתם של קרוסקל
- الگوریتم کراسکال
- خوارزمية كروسكال
- ขั้นตอนวิธีของครูสกาล
- クラスカル法
- 克鲁斯克尔演算法
- 크러스컬 알고리즘
- Subject
- Category:Articles containing proofs
- Category:Articles with example pseudocode
- Category:Graph algorithms
- Category:Greedy algorithms
- Category:Spanning tree
- Thumbnail
- WasDerivedFrom
- Kruskal's algorithm?oldid=1091274413&ns=0
- WikiPageLength
- 15208
- Wikipage page ID
- 53776
- Wikipage revision ID
- 1091274413
- WikiPageUsesTemplate
- Template:Harvtxt
- Template:Isbn
- Template:Reflist
- Template:Short description
