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

Lecture 17.docx

3 Pages
91 Views
Unlock Document

Department
Computer Science
Course
CSC263H1
Professor
Toniann Pitassi
Semester
Winter

Description
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


OR

Join OneClass

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

Sign up

Join to view


OR

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.


Submit