CSCA67H3 Lecture Notes - Lecture 6: Itch, Topological Sorting

• School: UTSC
• Department: Computer Science
• Course: CSCA67H3
• Professor: Anna Bretscher

Document Summary

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. Let w = {w1, w2, w3, w4, w5, w6, w7} be the set of webpages. Draw the graph: in this case there is an acceptable ordering. A: if webpages w8 and w5 are written rst, imagine deleting them from the graph. There are many ways to walk or traverse a graph. Usually, we start a walk at a source. Two very common graph traversals or searches are depth first search and breadth first search. If v has not been visited, visit v: if v has an unvisited neighbour x, visit x. Do dfs(x): if v has no unvisited neighbour, return to the previously vis- ited vertex z. Do dfs(z): how is dfs related to our webpage problem, let"s try a dfs on our graph starting at w1.