- Given connected Graph G with positive edge weights, find a min weight set of edges that connects all of the vertices.
- Application: - telephone, electrical, hydraulic, TV cable, computer, road
- It is a definition
- it should connect all nodes of graph
- the graph I’m concern should be weighed
- no cycles
- minimum possible total edge weight
- spanning is present participle of span, means to measure by hand and thumb extended
- krushkal Algo o(E log (v)) Kruskal MST
- prims Algo o(v^2) Prim’s algo MST
- Prim’s algorithm runs faster in dense graphs. Kruskal’s algorithm runs faster in sparse graphs. It generates the minimum spanning tree starting from the root vertex. It generates the minimum spanning tree starting from the least weighted edge