4.2 Depth first search Flashcards
1
Q
What is depth first search used for
A
- Finding path from x to y
- Explore the entire component of G containing x
2
Q
What is the core idea behind depth first search
A
- Explore first edge until no unexplored left, then backtrack and try edge 2 etc. (So long as the edge is unexplored)
3
Q
What is the psuedocode for DFS
A
4
Q
What is the time complexity for DFS
A
5
Q
Prove DFS explores every vertex in the component
A
In a strongly connected graph there exists a path from u to v
6
Q
Prove this for DFS
A
7
Q
What are the 2 properties of a DFS tree
A
