graph & tree traversal

• What is the process of graph traversals?

  Systematically visiting each node in the graph
• Why is it important to track visited nodes in graph traversals?

  To avoid revisiting nodes and infinite loops
• What are the three states for each node in graph traversals?

  • Unvisited
  • Discovered
  • Visited
• What is the primary use of breadth-first search in graph traversal?

  To find the path with the least nodes
• What data structure does breadth-first search use?

  A queue
• How does breadth-first search explore nodes?

  It explores all adjacent nodes before moving on
• What is the main purpose of depth-first search?

  To determine if a path exists between two nodes
• What does it mean for a graph to not be fully connected?

  Some nodes may not have direct paths to others
• How does depth-first search proceed through the graph?

  It searches as far down a branch as possible
• What happens if the target node is not found during depth-first search?

  The algorithm backtracks to explore other branches
• What data structure does depth-first search use?

  A stack
• What is added to the stack during depth-first search?

  Each discovered node