6.006 Q2 Topological Sort / Transformation

Front 1

(Spring 2011) Every directed acyclic graph has exactly one topological ordering.

Back 1

False. Some priority constraints may be unspecified, and multiple orderings may be possible for a given DAG. For example a graph G = (V, E) = ({a, b, c}, {(a, b), (a, c)}) has valid topological orderings [a, b, c] or [a, c, b]. As another example, G = (V, E) = ({a, b}, {}) has valid topological orderings [a, b] or [b, c].

Front 2

[Spring 2009] Topological sort requires Ω(V lg V ) if the edge weights are unbounded.

Back 2

False. This statement is almost complete nonsense; topological sort has nothing to do with weights. It takes Θ(V + E) time on any (unweighted) DAG.

Front 3

[Fall 2009] A directed graph with a negative weight cycle has a topological ordering.

Back 3

False

Front 4

[Fall 2009] If one can reach every vertex from a start vertex in a directed graph, then the graph is strongly connected.

Back 4

False

Front 5

[Fall 2009] Topological sort can be performed using one breadth-first search procedure on the graph.

Back 5

False

Front 6

[Fall 2009] Finding the strongly connected components in a graph requires Ω(V E) time where V is the number of vertices and E is the number of edges.

Back 6

False

Front 7

[Spring 2008] Every directed acyclic graph has only one topological ordering of its vertices.

Back 7

[Spring 2008] Every directed acyclic graph has only one topological ordering of its vertices.
False. Counterexample: the graph {(1,2), (1,3)} can be topologically sorted either [1,2,3] or [1,3,2].

Front 8

[Fall 2008] If a topological sort exists for the vertices in a directed graph, then a DFS on the graph will produce no back edges.

Back 8

True. Both parts of the statement hold if and only if the graph is acyclic.

Front 9

(Spring 2011) Consider a weighted directed graph G = (V, E, w) and let X be a shortest s-t path for s, t ∈ V . If we double the weight of every edge in the graph, setting w′(e) = 2w(e) for each e ∈ E, then X will still be a shortest s-t path in (V, E, w′).

Back 9

True. Any linear transformation of all weights maintains all relative path lengths, and thus shortest paths will continue to be shortest paths, and more generally all paths will have the same relative ordering. One simple way of thinking about this is unit conversions between kilometers and miles.

Front 10

What's the topological sort algorithm?

Back 10

1. Call DFS to compute finishing times for each vertex v
2. As each vertex is finished, insert it onto the front of a linked list
3. return the linked list of vertices.

Front 11

What's the time of topological sort?

Back 11

theta(V+E), since dfs takes theta(V+E)