GR1 Flashcards
A DAG has at least one ____ and one ____.
source, sink
In a topological ordering, which vertex comes first?
The vertex with the highest post order number
In a topological ordering, which vertex comes last?
The vertex with the lowest post order number.
So you order vertices by descending post order #.
Alternative method of topological ordering
- Find a sink, output it, and delete it.
2. Repeat step 1 until the graph is empty
Vertices V and W are ‘strongly connected’ if…
there is a path V –> W and W –> V
Undirected graphs have connected components, while directed graphs have ____.
strongly connected components
Definition of strongly connected component
maximal set of strongly connected vertices
Key property of metagraph of SCC
There are no cycles. => It’s a DAG!
Every directed graph is a …
DAG of its strongly connected components
In a general directed graph, the vertex with the ____ post # always lies in a ____ SCC.
highest, source
How do you find a sink vertex in a directed graph?
You construct a reverse graph and run DFS on it. The highest post number, which is a ‘source’ of the reverse graph, is the ‘sink’ for the original graph.
We take this mapping of ‘source’ vertices from the reversed graph and operate on them as ‘sink’ vertices on the original input graph.
After you find the ‘sink’ vertex, how do you find SCC?
From the sink vertex, you run DFS on it. Whatever vertices it touches are part of the component. Since it lies in a ‘sink’ SCC, we don’t have to worry about it going outside of its own SCC.
A graphs has a cycle iff it’s DFS tree has a ___
back edge
A graphs has a cycle iff it’s DFS tree has a ___
back edge