Class Notes (835,574)
Canada (509,252)
CSC263H1 (54)
Lecture 17

Lecture 17.docx

3 Pages
Unlock Document

Computer Science
Toniann Pitassi

BFS reminder Nodes to be explored | u… v | in. newly discovered nodes colour(v) = (white = not discovered, grey = discovered but not explored, black = discovered and explored) d[v] = length of discovery path s→v by BFS (s → u1 → u2 → … → v) δ [v] = length of shortest path s→v Lemma 0: After BFS(s), ∀v: δ (s,v) ≤ d[v] Want to show: Theorem: After BFS(s),∀v: δ (s,v) = d[v] Lemma 1: If u enters the Q before v, then d[u] ≤ g[v] Proof: Suppose by contra, L1 is false Let v be the first node that enters Q such that d[u] > d[v] for some node u that entered Q before v u =/= s because d[s] = 0 v =/= s because s is the first node in Q so u and v entered Q during the exploration of u' ad v', respectively d[u] = d[u'] + 1 since d[u] > d[v] d[v] = d[v'] + 1 u' =/= v' Since u is in Q before v u was discovered before v u' was explored before v' was explored u' entered Q before v' entered Q u' → … → v' → … → u → … → v d[u'] ≤ d[v'] d[u] ≥ d[v] d[u'] ≤ d[v'] d[u']
More Less

Related notes for CSC263H1

Log In


Join OneClass

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

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.