Graphs
This week: Representations and Breadth First Search
Today I am looking for 3 volunteers for a
demonstration.
You need to be willing to unmute and talk to
the class. Let me know in the chat if you want
to volunteer.
– You are not allowed to use a direct access table in
PS2 Q4
– Test 1 marks will be released by July 15th
– Test 1 remark submission deadline extended to July
19th
– PS1 remarking done – email if your grade has not
been returned
– No office hours July 20th (will resume July 23rd)
Announcements
How do we represent Graphs?
Zoom Demo Activity
Are these graphs the same or different?
How do we represent Graphs?
Zoom Demo Activity
How do we represent Graphs?
Zoom Demo Activity
How do we represent Graphs?
Zoom Demo Activity
How do we represent Graphs?
Zoom Demo Activity
Adjacency Lists
Chalk Talk
Adjacency Lists
Chalk Talk
Adjacency Matrix
Chalk Talk
Chalk Talk
Worksheet Q1 – Q6
Put your answer to Q4 into the Google Doc row for your group
http://tinyurl.com/csc2635
Chalk Talk
Breadth First Search
• Starting from ________ s in V, BFS ___________ every vertex v
__________ from s.
• In the process, we find paths from s to each reachable v
• Works on ____________ and _____________ graphs
• Keeping track of progress by colouring each vertex
• White
• Grey
• Black
Breadth First Search
• Keep track of
• _______________ of v in BFS tree
• ________________ from s to v
• ____________ vertices stored in Queue so they are handled in FIFO
order
• Use adjacency list order
Breadth First Search
Breadth First Search
Chalk Talk
s: a, f
a: b, e
b: c, d
c: d, e
d:
e: d, f
f:
Worksheet Q8 – Q10
Put your answer to Q8 and Q9 into the Google Doc row for your group
http://tinyurl.com/csc2635
BFS: Complexity
Each vertex is enqueued at most ___________ when it is ___________.
So, while loop iterates at most _______ times.
But, the ____________of each node is examined at at most __________
in total.
So total running time is ________________
BFS: Claim to find shortest paths
Define 𝛿(s, v) = minimum distance from s to v
Claim: At the end of BFS, d[v] = 𝛿(s, v)
Aside: later when we have weighted graphs we will define shortest path
differently. For now, all edges in the path count as 1.
Chalk Talk
Lemma 𝛿(s, v) ≤ 𝛿(s, u) + 1 for all (u,v) in E.
Proof Idea
Lemma d[v] ≥ 𝛿(s, v) for all v in V, at any point during BFS
Proof Idea
Lemma if Q = [v1, … vr], then d[vi] ≤ d[vi+1] for each i and
d[vr] ≤ d[v1] + 1
Proof Idea
Chalk Talk
Theorem: At the end of BFS, d[v] = 𝛿(s,v) for all v
Assume: d[v] > 𝛿(s,v) for some v with minimum 𝛿(s,v)
Chalk Talk
Chalk Talk
Chalk Talk