COMPSCI 61B Lecture Notes - Lecture 27: Directed Graph, Preorder, Call Stack
1 Jun 2017
School
Department
Course
Professor
Document Summary
Level-order: order of increasing distance from s, start point. Suppose we have tasks 0 through 7, where an arrow from v to w indicates that v must happen before w. Perform a dfs traversal from every vertex with indegree 0, not clearing markings in between traversals. Topological ordering is given by the reverse of the list. 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!) Initialize the fringe, a queue starting vertex s and mark that vertex. For each unmarked neighbor of v: mark, add to queue, set its edgeto = v. Our code examines vertices in increasing order from source. The fringe queue always consists of the following (for some k): >= 0 vertices of distance k from s, >= 0 vertices of distance k + 1 from s. Runs in v+e time and uses v space.
