Graph Traversal Algorithms Quiz

What is the primary data structure used in depth-first traversal?

• Queue
• Stack
• List
• Tree

In breadth-first traversal, which of the following best describes the order of node visits?

• Visit all adjacent nodes before moving deeper
• Visit nodes in a random order
• Visit nodes in a depth-first manner
• Visit nodes based on their weights

Which of the following is NOT a typical application of depth-first traversal?

• Job scheduling
• Finding a path in a maze
• Finding the shortest path
• Solving puzzles

What is the time complexity of both depth-first search (DFS) and breadth-first search (BFS) in a sparse graph?

• O(n)
• O(n²)
• O(n + e)
• O(e)

Which traversal method is typically used for unweighted graphs?

• Depth-first traversal
• Both methods
• Neither method
• Breadth-first traversal

When performing a depth-first traversal, what happens when a node has no unvisited adjacent nodes?

• The algorithm backtracks
• The algorithm terminates
• The algorithm continues to the next node
• The algorithm resets

Which of the following statements about graph representation is true?

• Graphs can only be represented using adjacency matrices
• Graphs cannot represent dead ends
• Graphs must be directed
• Graphs can be represented using lists or matrices

What is the main difference between depth-first and breadth-first traversal?

• DFS uses a queue, BFS uses a stack
• DFS is faster than BFS
• DFS explores as far as possible down a path, BFS explores all neighbors first
• BFS is used for weighted graphs

In the context of graph traversal, what does the term 'adjacent nodes' refer to?

• Nodes that are connected by an edge
• Nodes that have the same value
• Nodes that are at the same depth
• Nodes that are visited in the same traversal

Which traversal method would be more suitable for finding the shortest path in an unweighted graph?

• Depth-first traversal
• Both methods
• Breadth-first traversal
• Neither method