English
Menu

Data Structures and Algorithms

In a graph whose edges have no weights, you want to find the smallest number of edges from a starting vertex to every other vertex. Which pair of search method and data structure is suitable?

  1. ABreadth-first search with a queue
  2. BDepth-first search with a stack
  3. CBreadth-first search with a stack
Show answer and explanation

Answer: A. Breadth-first search with a queue

Breadth-first search visits vertices in order of distance: first those one edge from the start, then those two edges away, and so on. Adding each newly found vertex to the back of a queue and taking vertices from the front preserves this nearest-first order, so the number of edges when a vertex is first reached is the shortest. Depth-first search (using recursion or a stack) goes as far as it can along one path, so it may first reach a vertex by a roundabout route, and shortest distances are not guaranteed. Using a stack instead of a queue turns the traversal into something close to depth-first search.

  • A. Correct. A queue makes the search visit vertices nearest-first, which gives the smallest number of edges.
  • B. Depth-first search can first reach a vertex by a roundabout route, so it does not guarantee shortest distances.
  • C. With a stack, the most recently found vertex is examined first, so vertices are no longer visited nearest-first.
Practice this topic Back to topic

Related calculators

Dijkstra's algorithm calculatorCompute shortest paths and distances from a list of weighted edges, and follow each step of finalizing vertices in a table and a diagramSorting algorithm visualizerWatch 7 sorting algorithms (bubble, selection, insertion, shell, merge, quick and heap) step by step as bar charts, and compare their comparison and write counts

Books on Data Structures and Algorithms Ad

As an Amazon Associate I earn from qualifying purchases.

More Data Structures and Algorithms questions

  1. In an undirected graph, the neighbors of each vertex are A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. A recursive depth-first search starts from vertex A. The neighbors are examined in the order listed, and as soon as an unvisited vertex is found, the search moves to it. In what order are the vertices visited?
  2. In an undirected graph, the edge weights (distances) are S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3 and A−T: 6. Which shows the shortest path from S to T found by Dijkstra's algorithm and its length?
  3. Which condition on the graph is required for Dijkstra's algorithm to find correct shortest paths?
  4. Tasks A to E have the ordering constraints “A before C”, “B before C”, “C before D”, “B before E” and “E before D”. Which order satisfies all the constraints (a result of topological sorting)?
  5. A function f(x, y) is defined as “if y is 0, return x; otherwise return f(y, x mod y)”. When f(84, 36) is called, what is the return value, and how many times is f called, including the first call?