You will be designing and describing three different algorithms below. These alg

Question

You will be designing and describing three different algorithms below.  These algorithms must run in linear time (i.e., O(E+V) on an adjacency list and O(V2) on an adjacency matrix. Describe these algorithms either in terms of the algorithms for depth-first search, explore, topological sort, graph reversal, strongly connected components, and breadth-first search and/or in terms of algorithms that are the solutions to questions posed earlier in this quiz. (For example, you can assume a solution to #1 exists when designing an algorithm for #2.)

Do not design a brand new algorithm from scratch. You will receive no credit for this. If your solution involves iteration or recursion (other than in the helper algorithms listed above), you will receive no credit.

#1

Describe (in two or three sentences) a linear-time algorithm that examines a directed acyclic graph and either

returns a vertex from which there are paths to every other vertex in the graph (if such a vertex exists) or

reports that there is no such vertex (otherwise).

#2

Describe (in two or three sentences) a linear-time algorithm that examines a directed (but not necessarily acyclic) graph and either

returns a vertex from which there are paths to every other vertex in the graph (if such a vertex exists) or

reports that there is no such vertex (otherwise).

#3

Describe (in two or three sentences) a linear-time algorithm that examines a directed (but not necessarily acyclic) graph and either

returns a vertex to which there are paths from every other vertex in the graph (if such a vertex exists) or

reports that there is no such vertex (otherwise).

Explanation / Answer

Solution #1 - First do a DFS traversal of the dag and mark the vertex which finishes last. Then do another dfs traversal from the marked vertex. If all the vertices are visited in one iteration of the traversal, then it means that there exists a path from the marked vertex to all the other vertices, otherwise no such vertex exists.

Solution #2 - The same approach as mentioned in Solution #1 will work in any directed graph, acyclic or not.

Solution #3 - First reverse the graph, and then follow the same approach in the above solution. The vertex which has a path to all other vertices in the reversed graph, is the vertex which can be reached by all other vertices in the original graph

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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