What is the time complexity of Breadth-First Search (BFS) on a graph represented using an Adjacency List with V vertices and E edges?
BFS visits every vertex once O(V) and scans every adjacency list node O(E), giving total time complexity O(V + E).
Which data structure is primarily used to implement Breadth-First Search (BFS) iteratively?
BFS explores vertices level by level in First-In-First-Out (FIFO) order, requiring a Queue data structure.
Which data structure is naturally used to implement Depth-First Search (DFS) iteratively or implicitly during recursion?
DFS explores as deep as possible along each branch before backtracking, utilizing Last-In-First-Out (LIFO) stack operations.
What is the time complexity of Depth-First Search (DFS) on a graph represented by an Adjacency Matrix?
When using an adjacency matrix, checking neighbors for each vertex requires iterating over all V entries in its row, taking O(V) per vertex, so total time is O($V^2)$.
In a Depth-First Search (DFS) forest of a directed graph, which type of edge points from a vertex to an ancestor in the DFS tree and indicates the presence of a cycle?
A back edge connects a vertex to an ancestor in the current DFS call stack. The presence of a back edge in a directed graph is a necessary and sufficient condition for a cycle.