GR3: MST Flashcards
1
Q
Difference b/t tree and forest
A
…
2
Q
Kruskal’s Algorithm runtime
A
O(m logn)
3
Q
Kruskal’s Algorithm summary
A
- Sort edges in ascending weight
- for each edge in E
- if edge doesn’t create cycle
- add edge to set
- return set
4
Q
definition of a graph cut
A
a set of edges that partitions the graph into two subgraphs
5
Q
a tree on n vertices has exactly ____ edges
A
n-1
6
Q
which edge is considered when we are attempting to create a MST?
A
the edge with the minimum edge across the cut
