CS6515 Graduate Algorithm Exam 2
Practice Guide 2026
1. How does DFS on an Recording a vertex's connected component number (ccnum) during ex-
undirected graph out- ploration
put connectivity infor-
mation?
2. How does DFS on a prev array, which indicates the vertex that was explored just prior to the
graph output reacha- given node
bility information?
3. For the kinds of edges Back edges, which have
(z, w) in a DFS tree, what
is the only type that ex- post(z) < post(w)
hibits a different order
For the other types of edges (tree, forward, cross)
of post(z) and post(w),
post(z) > post(w)
and what is that rela-
tionship?
4. How do we know G has a cycle itt its DFS tree has a back edge.
whether a graph G has
a cycle based on its DFS
tree?
5. How do we topological- Run DFS, then order the vertices in decreasing order by postorder num-
ly sort a DAG? ber.
The key fact is that for any DAG (and directed graphs in general) the vertex
with the highest postorder number is a source.
6. What does it mean for Strongly connected - there is a path from u to v and from v to u
two vertices u and v
to be strongly connect- SCC - maximal set of strongly connected vertices
ed?
1/3
Practice Guide 2026
1. How does DFS on an Recording a vertex's connected component number (ccnum) during ex-
undirected graph out- ploration
put connectivity infor-
mation?
2. How does DFS on a prev array, which indicates the vertex that was explored just prior to the
graph output reacha- given node
bility information?
3. For the kinds of edges Back edges, which have
(z, w) in a DFS tree, what
is the only type that ex- post(z) < post(w)
hibits a different order
For the other types of edges (tree, forward, cross)
of post(z) and post(w),
post(z) > post(w)
and what is that rela-
tionship?
4. How do we know G has a cycle itt its DFS tree has a back edge.
whether a graph G has
a cycle based on its DFS
tree?
5. How do we topological- Run DFS, then order the vertices in decreasing order by postorder num-
ly sort a DAG? ber.
The key fact is that for any DAG (and directed graphs in general) the vertex
with the highest postorder number is a source.
6. What does it mean for Strongly connected - there is a path from u to v and from v to u
two vertices u and v
to be strongly connect- SCC - maximal set of strongly connected vertices
ed?
1/3