Graphs Continued
This week: Spanning Trees, Starting Disjoint Sets
Announcements
• PS2 grading is on-going
• W9 Quercus module Q9 regraded
• Which source vertices lead to a BFS tree of height 4?
• Posted tomorrow: Week 11 module
• Posted August 3rd: Review module
• Test 1 will be on Tuesday, August 10th (during lecture time)
• PS3 due August 19th (planning to post Sunday, August 1st)
Minimum Spanning Trees
Two ideas for our algorithm
• Take a _________ and remove ___________edges until
we have a _________
Minimum Spanning Trees
Two ideas for our algorithm
• Take a _________ and remove ___________edges until
we have a _________
• Start with nothing and ___________ from ___________
making a ______________ as we go, until we have
__________________
Greedy Minimum Spanning Tree
Theorem
If G is a connected, undirected, weighted
graph, T is a ________ of some MST of G,
and e is an edge ________________
whose ___________ are
_____________________________ then
e is safe for T
Theorem
If G is a connected, undirected, weighted graph, T is a subset of some
MST of G, and e is an edge of minimum weight whose endpoints are in
different connected components of T, then e is safe for T
Prim’s algorithm
Idea: pick a __________________ and _____________ by
___________________
At each step: _______________________________
Prim’s algorithm
Worksheet Q5 & Q6
Don’t forget to note your progress in the Google doc or in the chat.
http://tinyurl.com/csc2635
http://tinyurl.com/csc2635
Prim’s Algorithm
Chalktalk Tracing Prim’s Algorithm
Making Prim’s Algorithm Efficient
• For Queue, use
• Line 11?
Kruskal’s algorithm
Idea: Don’t build a _____________. Instead, build up a ____________.
At each step:
Pick ____________________
That does not _________________________
Kruskal’s algorithm
Idea: Don’t build a tree until the end. Instead, build a __________ and
At each step:
Pick _____________
That does not ________________
Kruskal’s Algorithm
Worksheet Q7
Report when you finish Q7 in the Google Doc row for your group or in
the chat. If you are watching the video, pause until you complete Q7.
http://tinyurl.com/csc2635
http://tinyurl.com/csc2635
Kruskal’s algorithm Complexity
What is the hard part of executing this efficiently?
Disjoint Set ADT
MAKE-SET(x):
FIND-SET(x):
UNION(x,y):
Kruskal’s Algorithm
Worksheet Solution