Determain graph has cycle
-
Approach 1: Do DFS from 0 (arbitrary vertex).
- Keep going until you see a marked vertex.
- Potential danger:
- 1 looks back at 0 and sees marked.
- Solution: Just don’t count the node you came from.
-
Worst case runtime: O(V + E) -- do study guide problems to reinforce this.
- With some cleverness, can give a tighter bound of O(V).
-
Approach 2: Use a WeightedQuickUnionUF object.
- For each edge, check if the two vertices are connected.
- If not, union them.
- If so, there is a cycle.
- For each edge, check if the two vertices are connected.
-
Worst case runtime: O(V + E α(V)) if we have path compression.
-
Here α(V) is the inverse Ackermann function from Disjoint Sets.