Prim's algorithm
In computer science, Prim's algorithm (also known as Jarník's algorithm) is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.
- Comment
- enIn computer science, Prim's algorithm (also known as Jarník's algorithm) is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.
- Depiction
- Has abstract
- enIn computer science, Prim's algorithm (also known as Jarník's algorithm) is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex. The algorithm was developed in 1930 by Czech mathematician Vojtěch Jarník and later rediscovered and republished by computer scientists Robert C. Prim in 1957 and Edsger W. Dijkstra in 1959. Therefore, it is also sometimes called the Jarník's algorithm, Prim–Jarník algorithm, Prim–Dijkstra algorithmor the DJP algorithm. Other well-known algorithms for this problem include Kruskal's algorithm and Borůvka's algorithm. These algorithms find the minimum spanning forest in a possibly disconnected graph; in contrast, the most basic form of Prim's algorithm only finds minimum spanning trees in connected graphs. However, running Prim's algorithm separately for each connected component of the graph, it can also be used to find the minimum spanning forest. In terms of their asymptotic time complexity, these three algorithms are equally fast for sparse graphs, but slower than other more sophisticated algorithms.However, for graphs that are sufficiently dense, Prim's algorithm can be made to run in linear time, meeting or improving the time bounds for other algorithms.
- Hypernym
- Algorithm
- Is primary topic of
- Prim's algorithm
- Label
- enPrim's algorithm
- Link from a Wikipage to an external page
- meyavuz.wordpress.com/2017/03/10/prims-algorithm-animation-for-randomly-distributed-points
- Link from a Wikipage to another Wikipage
- Adjacency list
- Adjacency matrix
- Array data structure
- Asymptotic computational complexity
- Big-O notation
- Binary heap
- Borůvka's algorithm
- Broadcasting (computing)
- Category:Articles containing proofs
- Category:Articles containing video clips
- Category:Articles with example pseudocode
- Category:Graph algorithms
- Category:Greedy algorithms
- Category:Spanning tree
- Computer science
- Computer scientist
- Connected component (graph theory)
- Czech people
- D-ary heap
- Dense graph
- Dijkstra's algorithm
- Distributed minimum spanning tree
- Edge (graph theory)
- Edsger W. Dijkstra
- Fibonacci heap
- File:Distributed adjacency matrix for parallel prim.png
- File:MAZE 30x20 Prim.ogv
- File:Prim's algorithm.svg
- File:Prim's algorithm proof.svg
- File:PrimAlgDemo.gif
- Flag value
- Graph theory
- Greedoid
- Greedy algorithm
- Heap (data structure)
- Kruskal's algorithm
- Linear time
- Linked list
- Minimum spanning tree
- Parallel algorithm
- Priority queue
- Pseudocode
- Reduction Operator
- Robert C. Prim
- Shortest path problem
- Sparse graph
- Time complexity
- Tree (graph theory)
- Undirected graph
- Vertex (graph theory)
- Vojtěch Jarník
- Weighted graph
- SameAs
- 4MhUQ
- Algorisme de Prim
- Algorithme de Prim
- Algorithmus von Prim
- Algoritma Prim
- Algoritme van Prim
- Algoritmo de Prim
- Algoritmo de Prim
- Algoritmo di Prim
- Algoritmul lui Prim
- Algorytm Prima
- Jarníkův algoritmus
- m.0f2jn
- Prim's algorithm
- Prim algoritması
- Prim-algoritmus
- Primov algoritem
- Primov algoritmus
- Prims algoritm
- Prims algoritme
- Q470813
- Thuật toán Prim
- Алгоритм Прима
- Алгоритм Прима
- Примов Алгоритам
- Примов алгоритам
- האלגוריתם של פרים
- الگوریتم پریم
- خوارزمية بريم
- ขั้นตอนวิธีของพริม
- პრიმის ალგორითმი
- プリム法
- 普林姆算法
- 프림 알고리즘
- Subject
- Category:Articles containing proofs
- Category:Articles containing video clips
- Category:Articles with example pseudocode
- Category:Graph algorithms
- Category:Greedy algorithms
- Category:Spanning tree
- Thumbnail
- WasDerivedFrom
- Prim's algorithm?oldid=1122630917&ns=0
- WikiPageLength
- 18367
- Wikipage page ID
- 53783
- Wikipage revision ID
- 1122630917
- WikiPageUsesTemplate
- Template:Commons category-inline
- Template:Ordered list
- Template:Reflist
- Template:Short description
