Question 1: Reachability

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(V²) 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.

We want to see if you can assemble a new algorithm out of old ones. Don't disappoint us!

a) 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).

Re-read the instructions at the beginning before starting.

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

• returns the set of all vertices from which there are paths to every other vertex in the graph (if such vertices exist) or
• reports that there are no such vertices (otherwise).

Re-read the instructions at the beginning before starting. You must use an algorithm for the previous problem as a major part of your solution.

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

• returns the set of all vertices to which there are paths from every other vertex in the graph (if such vertices exist) or
• reports that there are no such vertices (otherwise).

Re-read the instructions at the beginning before starting. You must use an algorithm for the previous problem as a major part of your solution.