MCQ IN COMPUTER SCIENCE & ENGINEERING

Detailed explanation-1: -The topological sorting of any DAG can be done in time. Explanation: Topological sorting can be done in O(V+E), here V and E represents number of vertices and number of edges respectively.

Detailed explanation-2: -Topological sorting forms the basis of linear-time algorithms for finding the critical path of the project, a sequence of milestones and tasks that controls the length of the overall project schedule.

Detailed explanation-3: -A topological sort is a linear ordering of vertices in a directed acyclic graph (DAG). Given a DAG G = (V, E), a topological sort algorithm returns a sequence of vertices in which the vertices never come before their predecessors on any paths.

Detailed explanation-4: -A topological sort of a DAG G = ( V, E ) is a linear ordering of v V such that if ( u, v ) E then u appears before v in this ordering. If G is cyclic, no such ordering exists: Topological sort can also be viewed as placing all the vertices along a horizontal line so that all directed edges go from left to right.

Detailed explanation-5: -Topological sort only works for Directed Acyclic Graphs (DAGs) Undirected graphs, or graphs with cycles (cyclic graphs), have edges where there is no clear start and end. Think of v-> u, in an undirected graph this edge would be v <–> u .