CS 6515: Graphs
Topological ordering, is a list where every
vertex appears after all vertices it de-
pends on. For the image attached, this
would be the topological ordering:
XYZWU
XYZUW
Topological Ordering? XYUZW
Strongly Connected Components.
A component is strongly connected if
there is a path between a source vertex
and a destination vertex, and a path from
What is SCC? the destination vertex back to the source
vertex.
Another way a component is strongly
connected, is if no other vertex can reach
it. (Sink vertex)
{A},{B,E},{C,F,G},{D},{H,I,J,K,L}
What are the SCC, in this graph? Graph
is in the definition.
Does v with lowest post # always lie in a
No.
sink SCC?
Does v with the highest post # always lie
Yes
in a source scc?
,CS 6515: Graphs
input: DAG = (V,E) in adj list:
1. Construct reverse graph
2. Run DFS on the Reverse Graph
SCC Algorithm 3. Order V(vertex) by post # in decreas-
ing order
4. Run undirected connected compo-
nents all on G
dfs(G):
for all v V :
visited(v) = false
for all v V :
if not visited(v): explore(v)
DFS (Graph) Algorithm
Runtime: O (|V| + |E|})
Input: G = (V,E) is a graph; v V
Output: visited(u) is set to true for all
nodes u reachable from v
visited(v) = true
previsit(v)
Explore Algorithm
for each edge (v, u) E:
if not visited(u): explore(u)
Tip: The previsit and postvisit procedures
are optional
Previi
Runtime: O (E)
, CS 6515: Graphs
previsit(v):
ccnum[v] = cc
Background Info: Check if a graph is con-
nected and, more generally, to assign
each node v an integer ccnum[v] identi-
fying the connected component to which
it belongs.
Previsit(Vertex) CC needs to be initialized to zero and
to be incremented each time the DFS
procedure calls explore.
previsit(v):
pre[v] = clock
clock = clock + 1
Time Orderings: with Previsit(vertex) and
Postvisit(vertex)
postvisit(v):
post[v] = clock
clock = clock + 1
Undirected Graph Edges
Topological ordering, is a list where every
vertex appears after all vertices it de-
pends on. For the image attached, this
would be the topological ordering:
XYZWU
XYZUW
Topological Ordering? XYUZW
Strongly Connected Components.
A component is strongly connected if
there is a path between a source vertex
and a destination vertex, and a path from
What is SCC? the destination vertex back to the source
vertex.
Another way a component is strongly
connected, is if no other vertex can reach
it. (Sink vertex)
{A},{B,E},{C,F,G},{D},{H,I,J,K,L}
What are the SCC, in this graph? Graph
is in the definition.
Does v with lowest post # always lie in a
No.
sink SCC?
Does v with the highest post # always lie
Yes
in a source scc?
,CS 6515: Graphs
input: DAG = (V,E) in adj list:
1. Construct reverse graph
2. Run DFS on the Reverse Graph
SCC Algorithm 3. Order V(vertex) by post # in decreas-
ing order
4. Run undirected connected compo-
nents all on G
dfs(G):
for all v V :
visited(v) = false
for all v V :
if not visited(v): explore(v)
DFS (Graph) Algorithm
Runtime: O (|V| + |E|})
Input: G = (V,E) is a graph; v V
Output: visited(u) is set to true for all
nodes u reachable from v
visited(v) = true
previsit(v)
Explore Algorithm
for each edge (v, u) E:
if not visited(u): explore(u)
Tip: The previsit and postvisit procedures
are optional
Previi
Runtime: O (E)
, CS 6515: Graphs
previsit(v):
ccnum[v] = cc
Background Info: Check if a graph is con-
nected and, more generally, to assign
each node v an integer ccnum[v] identi-
fying the connected component to which
it belongs.
Previsit(Vertex) CC needs to be initialized to zero and
to be incremented each time the DFS
procedure calls explore.
previsit(v):
pre[v] = clock
clock = clock + 1
Time Orderings: with Previsit(vertex) and
Postvisit(vertex)
postvisit(v):
post[v] = clock
clock = clock + 1
Undirected Graph Edges
