COMPSCI 61B Lecture Notes - Lecture 27: Topological Sorting, Stack Trace, Preorder
28 Aug 2017
School
Department
Course
Professor
Document Summary
Level-order: order of increasing distance from s (aka bfs) As we"ll soon see, many interesting graph problems have solutions that boil down identi cation of the right traversal (some are quite complex to describe and implement) Information to record as vertices are visited (e. g. edgeto and marked) Special actions to take on visit (e. g. quit if vertex t is seen) Perform a dfs traversal from every vertex with indegree 0, not clearing markings in between traversals, then reverse it. Can rewrite the graphin a line such that all the edges are pointing rightwards. This algorithm will actually work regardless of where you start (doesn"t have to be the indegree 0 vertices; you can just iterate through all the vertices) Goal: given the graph above, nd the shortest path from 0 to every other vertex. Level-order provides the shortest paths from 0 to every reachable vertex from 0 by de nition.
