CSC263H1 Lecture Notes - Lecture 9: Adjacency List, Color Field, Search Algorithm
18 Oct 2017
School
Department
Course
Professor
Document Summary
Csc 263 lecture summary for week 9 winter 2017. Each node enqueued at most once (when it is white), and colour changed to gray at same time. So main loop iterates at most o(n) times. But, adjacency list of each node examined at most once over entire run, so total running time is o(n + m) -- linear in size of adjacency lists. At the end of bfs, d[v] = \delta(s,v) = minimum distance from s to v = smallest number of edges on any s--v path. Lemma 22. 1: \delta(s,v) <= \delta(s,u) + 1 for all (u,v) in e. Proof idea: path s--u followed by edge (u,v) is one possible s--v path. Lemma 22. 2: d[v] >= \delta(s,v) for all v in v, at any point during bfs. Proof idea: induction on number of enqueue operations performed. Lemma 22. 3: if q = [v_1,,v_r], then d[v_i] <= d[v_{i+1}] for each i and d[v_r] <= d[v_1] + 1.
