Minimum Spanning Trees (cont)
Simplifying assumptions:
- edges in G are not directed
(MST for digraphs is harder)
- no edge weights are negative
- all edge weights are distinct
If edges may have same weight:
- MST may not be unique (not necessarily a problem)
- if we have to choose between edges with same weight ...
- greedy algorithms might make wrong choice
- might not end up with minimum cost solution
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}