English
Menu

Data Structures and Algorithms

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)?

  1. AA, C, B, E, D
  2. BB, A, E, C, D
  3. CB, E, D, A, C
Show answer and explanation

Answer: B. B, A, E, C, D

In B, A, E, C, D, A and B come before C, C and E come before D, and B comes before E, so all five constraints are met. A, C, B, E, D does C before B, violating “B before C”, and B, E, D, A, C does D before C, violating “C before D”. Topological sorting arranges the vertices of a directed acyclic graph (DAG) so that every edge points from earlier to later; it can be done by repeatedly taking a vertex with no incoming edges (Kahn's algorithm) or with depth-first search. The answer is not always unique: this example has five valid orders.

  • A. It does C before B, violating “B before C”.
  • B. Correct. It satisfies all five constraints.
  • C. It does D before C, violating “C before D”.
Practice this topic Back to topic

Related calculators

Sorting 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 countsDijkstra'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 diagram

Books on Data Structures and Algorithms Ad

As an Amazon Associate I earn from qualifying purchases.

More Data Structures and Algorithms questions

  1. 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?
  2. A function fib(n) for Fibonacci numbers is defined recursively as “if n is 1 or less, return n; otherwise return fib(n−1) + fib(n−2)”. When fib(5) is called, how many times is fib called, including the first call?
  3. You pay 8 yen with coins of 1 yen, 4 yen and 6 yen. Which correctly relates the number of coins chosen by a greedy algorithm, which uses as many of the largest coin as possible first, to the minimum number of coins?
  4. A knapsack with capacity 8 is filled with items chosen from four items with (weight, value) of (2, 3), (3, 4), (4, 5) and (5, 6). There is only one of each item and items cannot be split. What is the maximum total value with a total weight of 8 or less?
  5. Which is a characteristic of the Boyer-Moore algorithm for finding a pattern in a string?