Let be a directed graph whose vertex set is the set of numbers from 1 to 100 . There is an i j edge from a vertex to a vertex if and only if j = i + 1 j = 3i either or . The minimum G number of edges in a path in from vertex 1 to vertex 100 is ____
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: D. 7 L = L ∩ L
Explanation
Working backwards from 100: 100 ← 99 ← 33 ← 11 ← 10 ← 9 ← 3 ← 1. The path 1 → 3 → 9 → 10 → 11 → 33 → 99 → 100 uses 7 edges.
More Data Structures and Algorithms questions
- The running time of an algorithm is O(g(n)) if and only if: (A) its worst-case running time is O(g(n)) and its best-case running time is Ω(…
- Match List I with List II. List I: A. Topological sort of a DAG, B. Kruskal's MST algorithm, C. Bellman-Ford single-source shortest path, D…
- Consider the undirected graph below: Using Prim's algorithm to construct a minimum spanning tree starting with node a, which one of the fol…
- G T Let be a simple undirected graph, D be a DFS G T tree on , and B be the BFS tree on G. Consider the following statements. G Statement I…
- The weight of minimum spanning tree in graph G, calculated using Kruskal's algorithm is :
- What is the worst case running time of Insert and Extract-min, in an implementation of a priority queue using an unsorted array? Assume tha…