1. The following matrix was produced by Warshall’s algorithm with successors. Ho

ID: 3576279 • Letter: 1

Question

1. The following matrix was produced by Warshall’s algorithm with successors. How many edges are on the represented path from 3 to 1?

-1 3 3 3 3

-1 3 3 3 4

-1 1 1 1 4

-1 2 2 2 2

-1 -1 -1 -1 -1

_____ A. 0 B. 1 C. 2 D. 3

2. What is the purpose of the first depth-first search when finding strongly connected components?

A. To assure that two vertices, X and Y, with paths from X to Y but not from Y to X, are output in different components.

B. To assure that two vertices that are in the same cycle will be output in the same component

C. To assure that two vertices with no paths between them are not output in the same component

D. To make sure that the input graph has no cycles.

3. The worst-case time for depth-first search is:

A. theta(V log E) B. theta(E log V) C. theta(V log V) D. theta(V + E)

Q2) Ans 'B': To assure that two vertices that are in the same cycle will be output in the same component

Q3)Ans 'C': theta(V+E)

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.