Exam 2 Flashcards
Study for exam 2
What must be present if there’s a back edge?
There must be a cycle in the graph if the DFS tree has a back edge
What is a DAG and what are its characteristics?
directed acyclic graphs
every vertex u where there is an edge to vertex v has one direction
has no cycles in the graph
Can be topologically sorted
Must have one or more source vertex
Must have one or more sink vertex
What is an alternative topological sorting algorithm?
Alternative topological sorting:
Find a sink vertex, output it, and then delete
Repeath this first step until the graph is empty
How do we find a sink vertex in a DAG?
Find the lowest postorder number vertex in a DAG
What is the pseudocode for the SCC algorithm?
 construct a reverse G of the original input graph G
 run DFS on G reverse
 order V by decreasing post order number
 run undirected connected components alg on G
What are the types of edges in a graph?
forward edge  is a forward edge if it points from a vertex to one of its descendants in the DFS tree, but is not a tree edge
 pre(u) < pre(v)
 post(u) > post(v)

back edge  an edge uv is a back edge if it points from a vertex to one of its ancestors in the DFS tree
 creates a cycle in the DFS tree
 pre(u) > pre(v)
 post(v) > post(u) (only one where this is the case)
tree edge  edge uv is a tree edge if v is a direct descendent of u in a DFS tree
 part of the DFS tree
 pre(u) < pre(v)
cross edge  edge uv is a cross edge if it connects two vertices that are neither in a direct ancestordescendant relationship nor part of the same DFS tree
 pre(u) and pre(v) have no distinct relationship
 the finish time of u and v also have no distinctive relationship

How do you find connected components in an undirected graph G? What is the runtime for doing this? What is the pseudocode?
Run DFS and keep track of component numbers #
O(n+m)
Psuedocode:
 Running explore from vertex
 Store z as visited because its the first time visiting
 Also store z in the current count for the connected components
 Now explore neighbors of z
If w or neighbor hasn’t been visited, the we call explore on that neighbor (recursively)
How can we use DFS to find a path between 2 vertices?
Run DFS and populate the previous values for each vertex in a previous array
We then have the previous array and use this to find a path between the pair of connected vertices
How do we find connectivity info on a directed graph?
We run DFS on the directed graph and add pre/post order numbers
Specifically:
We use clock values to track the pre and post orders
When first visiting vertex z, we store the preorder number
After visiting / exploring vertex z, we store the postorder number
What is required for there to be a cycle in a DFS tree?
There must be a back edge
Does a DAG have cycles or back edges
No cycles, no back edges
What happens when we topologically sort a DAG? Can there be more than one topological orderings?
Topological sort > ordering from vertices from lower numbers to higher numbers
All edges should go from higher postorder number to lower postorder number
Thus, we order vertices by decreasing post order number
All post order numbers range between 1 and 2n
Therefore, we make an array of size 2n and insert each vertex in to the array in the appropriate place based on their post order number. We then iterate from highest to smallest and output the vertices. This step takes linear time
Yes, there can be more than one topological orderings
What are the source and sink vertices? How many do a DAG have?
Source = no incoming vertices; highest post order #
Sink = no outgoing edges; lowest post order #
Every DAG has one or more sink vertices
Vertices u and v are strongly connected if …
and only if there is a path u to v and v to u
How are SCC’s for an undirected graph found?
We find the SCC components in topological order
We visit any vertex from the sink vertex and visit nothing else
Then we find the strongly connected component
This even works for vertices like A where there are no other vertices in the SCC and they reach the whole graph
But once we find a sink vertex, we can run explore and get all parts of the SCC