COMPUTER SCIENCE AND ENGINEERING
COMPILER DESIGN
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
All the Cyclic Directed Graphs have topological sorting
|
|
|
All the Acyclic Directed Graphs have topological sorting
|
|
|
All Directed Graphs have topological sorting
|
|
|
All the cyclic directed graphs have non topological sorting
|
Detailed explanation-1: -Which of the given statement is true? Explanation: Cyclic Directed Graphs cannot be sorted topologically.
Detailed explanation-2: -A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time.
Detailed explanation-3: -Topological sorting is a linear ordering defined for vertices of a directed acyclic graph (DAG). For every directed edge (u, v), vertex u comes before vertex v in the topologically sorted order. This means that topological sorting for a cyclic graph is not possible.
Detailed explanation-4: -A topological sort can only ever be applied to directed acyclic graphs, or DAGs. It is impossible to run a topological sort on a directed graph with a cycle, since it is unclear where the sort itself should start. There are a few different ways to actually implement topological sort.
Detailed explanation-5: -The topological sorting for a directed acyclic graph is the linear ordering of vertices.