Depth_First_Search_Flashcards
Front
Back
What is the main idea behind DFS?
DFS explores as deep as possible along each branch before backtracking.
What data structure is typically used to implement DFS?
A stack or recursion (implicitly using the call stack).
What are the key attributes tracked for each node in DFS?
Seen (visited), Parent, Discovery Time, Finish Time.
What is the purpose of discovery time in DFS?
It marks when a node is first visited.
What is the purpose of finish time in DFS?
It marks when all descendants of a node have been fully explored.
How does DFS handle disconnected graphs?
It runs DFS from each unvisited node (using an outer loop), forming a DFS forest.
What is a DFS Tree?
A tree formed from edges used to discover new nodes during DFS.
What is a DFS Forest?
A collection of DFS trees created when the graph is disconnected.
What are the four types of edges in DFS?
Tree Edge, Back Edge, Forward Edge, Cross Edge.
What defines a Tree Edge in DFS?
An edge used to first discover a node.
What defines a Back Edge?
An edge from a descendant to an ancestor in the DFS tree.
What defines a Forward Edge?
An edge from an ancestor to a non-child descendant.
What defines a Cross Edge?
An edge between nodes in different DFS branches (neither ancestor nor descendant).
How can discovery and finish times identify a Back Edge (u → v)?
v.d < u.d < u.f < v.f
How can discovery and finish times identify a Forward Edge (u → v)?
u.d < v.d < v.f < u.f
How can discovery and finish times identify a Cross Edge?
The intervals [u.d, u.f] and [v.d, v.f] are disjoint.
What DFS edge type is critical for detecting cycles?
Back Edge — if one exists, the graph has a cycle.
What is the DFS-based method to check if a graph contains a cycle?
Run DFS and check for any back edges.
What makes DFS useful in graph algorithms?
It enables cycle detection, topological sorting, and identification of graph components.
