Class Notes (806,817)
CSCA67H3 (56)
Lecture 6

# Week 6 - Topological Sort.pdf

6 Pages
315 Views

School
University of Toronto Scarborough
Department
Computer Science
Course
CSCA67H3
Professor
Anna Bretscher
Semester
Fall

Description
Topological Orderings Problem. Your company needs a new website. There will be many pages with links between them. The public is itching to view your website so you want to publish each page as soon as it is ready. Caveat: You don’t want any broken links. Q. What order do you create the pages in? Example. Let W = fw ;w1;w 2w ;3 ;4 ;w5g b6 th7 set of webpages. Suppose that: ▯ page w 1inks to pages fw ;2 ;w3;w 6, 7 ▯ pages w 3nd w li4k to page w , 8 ▯ pages w 2nd w li7k to page w an5 ▯ page w 6inks to pages w a2d w . 4 Q. In order that there are no broken links, in which order should the pages be written? A. 1 Q. How can we think of this problem as a graph? A. Draw the graph. Q. In this case there is an acceptable ordering. If there were no acceptable ordering, what property would the graph have? A. 2 Q. What do you notice about w and 5 w 8 5 6 A. 7 These types of vertices are called sinks. 4 1 8 Q. What do you notice about w ? 1 3 2 A. These types of vertices are called sources. Q. Which type of vertices (webpages) should be written ﬁrst? A. Q. If webpages w and w are written ﬁrst, imagine deleting them 8 5 from the graph. What do you notice about w ;w ;w 4nd w2? 3 7 A.
More Less

Related notes for CSCA67H3

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.