Class Notes (835,430)
CSC263H1 (54)
Lecture 16

# Lecture 16.docx

2 Pages
98 Views

Department
Computer Science
Course
CSC263H1
Professor
Toniann Pitassi
Semester
Winter

Description
Graph Search - Start at some node and explore it by following its edges to discover new nodes - explore newly discovered nodes etc 2 Types of graph searches 1) breadth - first. search(BFS) -- use adjacency list with this graph a) explore s: follow edges out of s to discover new nodes b) Explore nodes in the order they were discovered: first discovered first explored v ∈ V colour(v) = white means its not discovered colour(v) = grey means its discovered colour(v) = black means it was discovered and explored P(v) = u iff "u discovered v" (parent of v) s → u1 → u2 → … → u → v d[v] = d[u] + 1 (length/ number of edges of v is u + 1) G=( v, e), BFS(0, s) co
More Less

Related notes for CSC263H1
Me

OR

Join OneClass

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

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.