CS计算机代考程序代写 algorithm Announcements

Announcements

Announcements

• Homework 0 Solutions online

• Homework 1 Due on Friday

• Exam 1 Next Friday

– If you cannot take the exam during class hours,
please email me at letting me
know what times might work for you.

mailto:

Strongly Connected Components

Definition: In a directed graph G, two vertices v
and w are in the same Strongly Connected
Component (SCC) if v is reachable from w and
w is reachable from v.

Today

• Metagraphs

• Computing strongly connected components

• Shortest path algorithms (Ch 4)

Connectivity

• Do strongly connected components
completely describe connectivity in G?
– No! In directed case, can have edges between

SCCs.

• Need extra information to describe how SCCs
connect.

v w

Metagraph

Definition: The metagraph of a directed graph G
is a graph whose vertices are the SCCs of G,
where there is an edge between C1 and C2 if
and only if G has an edge between some
vertex of C1 and some vertex of C2.

Example

A B C

D E

F G

H

BCDE A

H

G F Note: Metagraph is a DAG!

Result

Theorem: The metagraph is any directed graph
is a DAG.

Proof (sketch):

• Assume for sake of contradiction it is not.

• Then metagraph has a cycle.

• Use this to show that separated components
should be connected.

Proof
G MG

A B

C

D

E

A B

C

D

E

Computing SCCs

Problem: Given a directed graph G compute the
SCCs of G and its metagraph.

Easy Algorithm:

• For each v compute vertices reachable from v.

• Find pairs v, w so that v reachable from w and
visa versa.

• For each v the corresponding w’s are the SCC of v.

Runtime: O(|V|(|V|+|E|)). We can do better.

Observation

Suppose that SCC(v) is a sink in the metagraph.

• G has no edges from SCC(v) to another SCC.

• Run explore(v) to find all vertices
reachable from v.

– Contains all vertices in SCC(v).

– Contains no other vertices.

• If v in sink SCC, explore(v) finds exactly v’s
component.

Strategy

• Find v in a sink SCC of G.

• Run explore(v) to find component C1.

• Repeat process on G-C1.

Problem: How do we find v?

Result

Proposition: Let C1 and C2 be SCCs of G with an
edge from C1 to C2. If we run DFS on G, the
largest postorder number of any vertex in C1
will be larger than the largest postorder
number in C2.

C1

C2

Why do we Care?

• Let v be the vertex with the largest postorder
number.

– There is no edge to SCC(v) from any other SCC.

– SCC is a source SCC.

• But we want a sink SCC.

• A sink is like a source, only with the edges
going in the opposite direction.

Reverse Graph

Definition: Given a directed graph G, the reverse
graph of G (denoted GR) is obtained by
reversing the directions of all of the edges of
G.

A

B

C A

B

C

Question: Reverse Graph Properties

Which of the following are true about reverse
graphs?

A) G and GR have the same number of vertices.

B) G and GR have the same number of edges.

C) G = (GR)R.

D) A vertex has as many ingoing/outgoing edges
in G as it does in GR.

Other Properties of Reverse Graphs

Given a directed graph G and its reverse graph
GR:

• G and GR have the same SCCs.

• The sink SCCs of G are the source SCCs of GR.

• The source SCCs of G are the sink SCCs of GR.

So we can find a sink SCC of G, by finding a
source SCC of GR!

Proposition Reminder

Proposition: Let C1 and C2 be SCCs of G with an
edge from C1 to C2. If we run DFS on G, the
largest postorder number of any vertex in C1
will be larger than the largest postorder
number in C2.

C1

C2

Proof I

If DFS discovers a vertex in C1 before C2:

• First vertex discovered is v.

• All of C1 and C2 downstream of v.

• DFS will discover the rest of C1 and C2 while
exploring v.

• v has largest postorder in C1 or C2.

Proof II

If DFS discovers a vertex in C2 before C1:

• First vertex discovered is w.

• DFS will find all of C2 while exploring w.

• C1 cannot be reached from w.

– Otherwise they’d be the same SCC.

• Every vertex in C1 discovered after w
finished.

• C1 has larger posts than C2.

C1

C2
w

Algorithm

SCCs(G)

Run DFS(GR) record postorder

Find v with largest v.post

Set all vertices unvisited

Run explore(v)

Let C be the visited vertices

Return SCCs(G-C) ∪ {C}

O(|V|+|E|)

Final Runtime: O((|V|+|E|)(#SCCs))

Still Too Slow

Problem: We recompute the postorder for every
SCC we need to find.

Solution: We don’t have to do this. After
removing some SCCs to get G’, the largest
postorder number of vertices in G’ is still in a
sink component of G’.

Algorithm II

SCCs(G)

Run DFS(GR) record postorders

Mark all vertices unvisited

For v ∈ V in reverse postorder

If v not in a component yet

explore(v) on

G-components found,

marking new component

If not v.visited

explore(v) mark component

Just 2 DFSs! Runtime O(|V|+|E|).

Example

A B C

D E

F G

H

1

2

3

4

5 6

7
8

9

10

11

12

13

14

15

16