CS计算机代考程序代写 Graphs

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