L14 (Connectivity, DAGs and Topo Sort) Flashcards
An undirected graph is “connected” under what condition?
If there is a path between all pairs of vertices Vi, Vj
What is a “connected component” in an undirected graph G?
A connected component is a subgraph of G (any graph whose vertex and edges are subsets of G) such that:
1. the subgraph is connected, and
2. no vertex in the subgraph is connected to any vertex outside
We can count the number of connected components in a graph using DFS/BFS by adding what modification?
Adding a global counter and a hashSet, and pruning whenever a visited node is re-visited
What do the pre-visit and post-visit ordering mean in DFS/BFS in the context of a clock?
pre-visit: the “time” that explore is first called on a vertex
post-visit: the “time” that the explore call is finished
Combining these two, we get a time interval
- What is a cycle in a graph?
- Under what condition is a graph considered a “tree”?
- Under what condition is a graph considered a “forest”?
- A cycle in a graph is a path that starts and ends at the same vertex
- A graph is considered a tree if it is connected AND does not contain any cycles
- A graph is considered a forest if does not contain any cycles (a collection of trees)
What is a DFS forest?
It is the collection of rooted trees that gets created when running a DFS on a graph
Write an algorithm to check if a directed graph G contains a cycle
- For each node, build a DFS forest
- If there are any duplicate nodes (or back edges) in any of the DFS forests, then there is a cycle
What is Topological Ordering. Is it possible to have this for cyclic graphs?
Topological Ordering is an ordering of vertices such that for each edge (u, v) in the graph, the vertex ‘u’ comes before the vertex ‘v’ in the ordering. This is not possible for cyclic graphs
If we perform a topological sort on a graph, what can we say about the post-visit values of the result?
It will be descending in post-values. The vertex with the highest “post” number will come first, and the vertex with the lowest “post” value will come last
What does it mean for a graph to be “Strongly connected”?
A graph is strongly connected if for every pair of vertices “u” and “v”, there is a directed path from “u” to “v” and “v” to “u”
What does it mean for a graph to be “Weakly connected”?
A graph is weakly connected if it is connected when the direction on each edge is ignored (it becomes an undirected graph)
What is a “strongly connected component” in a graph G?
A subgraph of the graph G which is strongly connected (there is a path from vertex U to V for every pair of vertices U and V)
What is a tree edge?
(u, v) is a tree edge if it is in the DFS forest, and v is visited in between the pre-visit and post-visit of u
What is a forward edge?
(u, v) is a forward edge if it is NOT in the DFS edge, and v is visited in between pre-visit and post-visit of u
What is a back edge?
(u, v) is a back edge if v is an ancestor of u, and u is visited in between pre-visit and post-visit of v
