5.5.2 Minimum spanning trees .o Definition 24: A minimum spanning tree in a connected weighted graph is a spanning tree that has the smallest possible sum of weights of its edges. ☆ Prim algorithms 冷 Kruskal’ s algorithms
5.5.2 Minimum spanning trees ❖ Definition 24: A minimum spanning tree in a connected weighted graph is a spanning tree that has the smallest possible sum of weights of its edges. ❖ Prim algorithms ❖ Kruskal’s algorithms
☆1.Prim' s algorithms &o Let t=e where e is minimum-weighted edge in G ◆fori=lton-2 &o begin e an edge of minimum weight incident to a vertex in T and not forming a simple circuit in T if added to T 令T:=TU{e end
❖ 1.Prim’s algorithms ❖ Let T={e} where e is minimum-weighted edge in G ❖ for i=1 to n-2 ❖ begin ei= an edge of minimum weight incident to a vertex in T and not forming a simple circuit in T if added to T ❖ T:=T∪{ei } ❖ end
6 5 v?C Theorem 5.17: Prim's algorithm produces a minimum spanning tree of a connected weighted graph
Theorem 5.17: Prim’s algorithm produces a minimum spanning tree of a connected weighted graph
令2 Kruskal’ s algorithn 令T=② 今Fori=1ton-1 ☆ begin o e= an edge of minimum weight in E(G)-E(T) and not forming a simple circuit in T if added to T 令T:=TU{e ☆cnd
❖ 2.Kruskal’s algorithm ❖ T=. ❖ For i=1 to n-1 ❖ begin ❖ ei= an edge of minimum weight in E(G)-E(T) and not forming a simple circuit in T if added to T ❖ T:=T∪{ei } ❖ end
3 6 5 5 2 5 5 yi