9.3 (Graph Traversal) Flashcards
What is a sequence of vertices linked by edges?
path
What is the maximal set of vertices that are connected?
connected component
An algorithm that checks __________ can be instrumented to report a path between the two vertices.
reachability
A path is a ________ that two vertices are connected
witness
What is it called when finding a witness?
search problem
What is it called when checking a witness?
verification problem
For Depth-First Search, what is the total time complexity for adjacency list representation?
O(V+E)
For Depth-First Search, what is the total time complexity for adjacency matrix representation?
O(V^2)
Which representation is more efficient for sparse graphs?
Adjacency List
Adjacency Matrix is inefficient unless the graph is dense (___ = ____)
(E=V^2)
What are the two implementations of Depth-First Search?
Recursive DFS and Stack-based DFS
Which type of Depth-First Search (DFS) uses the call stack to track visited nodes?
Recursive DFS
Which type of Depth-First Search (DFS) uses an explicit stack instead of recursion?
Stack-based DFS
What kind of array tracks the vertices either already examined or queued up to be examined?
mark array
All vertices above the frontier are _________.
explored
All vertices below the frontier are ________.
unexplored
True or false: every path from a start to a target goes through the frontier.
true
For Breadth-First Search, what is the total time complexity for adjacency list representation?
O(V+E)
For Breadth-First Search, what is the total time complexity for adjacency matrix representation?
O(V^2)
What are the two implementations of Breadth-First Search?
Queue-based BFS and Recursive DFS
Which BFS implementation uses a queue (FIFO) to track visited nodes?
Queue-based BFS
Which BFS implementation uses recursion instead of an explicit queue?
Recursive DFS
