a topological sort can be done on a cyclic graph.
Select the correct definition. Topological sorting:
A) Given a cyclic digraph find a linear ordering of vertices such that for all edges (v, w) in E, v procedes w in the ordering.
B) Given an acyclic undirected graph find a linear ordering of nodes such that for all vertices (v, w) in E, v proceeds w in the ordering
C) Given an acyclic digraph find a quadratic ordering of nodes such that for all edges (v, w) in E, v proceeds w in the ordering.
D) Given an acyclic digraph find a linear ordering of nodes such that for all edges (v, w) in E, v proceeds w in the ordering.
What is Topological Sorting?
It is finding an ordering of an acyclic graph such that all edges proceed in order.
none of the above
What is not part of algorithm for topological graph?
A. make a copy of the diagram
B.make a list l
C.make a q list
D.none of the above
Any linear ordering of all of the vertices in which all the arrows go to the right is a valid solution. The statemen is an example of:
A.Big o notation
B.Ascending
C.Topological
D.Descending
In the topological algorithm once you select a vertex V with an out outdegree of 0, where do you place the V in the list?
A) to the front of the list
B) the end of the list
C) the middle of the list
The algorithm for topological sorting includes
a. making a copy of the graph
b. initializing a list
c. selecting a vertex with an out degree of 0
d. all of the above.
What is any linear ordering of all of the verticies of a graph in which all the arrows go to the right is a valid solution?
A) Topological Sorting
B) Top-Down Sorting
C) Quick Sorting
D) None of the above
Any linear Ordering of all vertices where all the arrows point to the left is a valid solution
In order to perform a topilogical sort, the graph must be:
A. Cyclic
B. Acyclic
C. A tree
D. None of the above
For any given directed acyclic graph, there could be ______ valid topological sorts.
A. only one
B. only two
C. many
D. none - topological sorts only work in cyclic graphs
In an example of topological orders, which of the following is correct?
A. any nonlinear ordering of all of the vertices in which all the arrows go to the right
B. any linear ordering of all of the vertices in which all the arrows go to the right
C. any linear ordering of all of the vertices in which all the arrows go to the left
D. any linear ordering of all of the vertices in which all the arrows are static
Is topological sorting possible if and only if the graph has no directed cycles?
Is the example topological orders true or false?
Any linear ordering of all of the vertices in which all the arrows go to the right is a valid solution.
Given this sudo-method:
list digraph::topoSort() { // make a copy of digraph G // make a list l // for each vertex in G // select a vertex v with an outdegree of 2 // add v to the front of l // delete v and it's edges from the digraph }
What is the problem with this method?
When selecting a vertex to add to the sorted list, you must select a vertex with an outdegree of 0.
