21.1.2. Executing the Algorithm by Hand

Try these first

1. 1.

   What is Depth-First Search?

   Hint

   Think about how DFS starts its exploration.

2. 2.

   Describe what a stack is used for in DFS.

   Hint

   Consider the last vertex added to the stack.

3. 3.

   What does Depth-First Search do?

   • Explores all vertices at once
   • Explores as far as possible before backtracking
   • Is not used for graph traversal

   Hint

   Think about how it approaches exploration compared to BFS.

4. 4.

   Does DFS always find the shortest path in a graph?

   • True
   • False

   Hint

   Recall how DFS navigates the graph compared to BFS.

5. 5.

   Using DFS, find all connected components in a given undirected graph and demonstrate how to apply the algorithm.

   Hint

   Visualize the graph and ensure you revisit all possible starts.

6. 6.

   Graph G is constructed with vertices 1-10. Execute DFS and note all pre and post numbers, then identify any cut vertices.

   Hint

   Focus on the connections and transitions between vertices during the DFS process.