CS计算机代考程序代写 algorithm Graphs Continued

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