enter image description here
i think that this quastion have a liniar complexity solution ; i will addd the algorithm of procedure Prim(G, w):
input: גרף G עם קבוצת צמתים V וקבוצת קשתות E, פונקציית משקל w
output: עץ פורש מינימלי T
let T be a set of edges initially empty
let U be a set of vertices initially containing any vertex (e.g., V_0)
while U does not contain all vertices of G:
find edge (u, v) with minimum weight such that u is in U and v is not in U
add v to U
add (u, v) to T
return T
Using a Binary Heap:
𝑂(𝐸log𝑉)
O(ElogV)
Using a Fibonacci Heap:
𝑂(𝐸+𝑉log𝑉)
O(E+VlogV)
Using a Fibonacci heap provides a better asymptotic complexity, especially for dense graphs where 𝐸
E is much larger than 𝑉
V. For practical purposes and simpler implementations, the binary heap is often used despite its slightly worse complexity.
Yasmeen Phone is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
2