Directed Graphs

Vertex = taxi pickup; edge = taxi ride.

http://blog.uber.com/2012/01/09/uberdata-san-franciscomics/

DFS enables direct solution of simple digraph problems.

• ・ Reachability. ・ consin we Path finding. ・ Topological sort. ・ Directed cycle detection. Basis for solving difficult digraph problems. ・ 2-satisfiability. ・ Directed Euler path. ・ Strongly-connected components. SIAM J. COMPUT. Vol. 1, 2, No. June 1972 DEPTH-FIRST SEARCH AND LINEAR GRAPH ALGORITHMS* ROBERT TARJAN" Abstract. The value of depth-first search "bacltracking" technique for solving problems is or as a An improved version of an algorithm for finding the strongly connected illustrated by two examples. components a directed of graph and ar algorithm for finding the biconnected components an un-of direct graph are presented. The space and time requirements of both algorithms are bounded by k 1V d-+ k2E k for some constants kl, k2, and k where number of and E number Vis the vertices is the a, of edges of the graph being examined. Key words. Algorithm, backtracking, biconnectivity, connectivity, depth-first, graph, search, spanning strong-connectivity. tree,

Observation. DFS visits each vertex exactly once. The order in which it does so can be important.

Orderings.

・

Preorder: order in which dfs

is called.

・

Postorder: order in which dfs

returns.

・

Reverse postorder: reverse order in which dfs

returns.

private void dfs(Graph G, int v) { marked[v] = true; preorder.enqueue(v); for (int w: G.adj(v)) if (!marked[w]) dfs(G, w); postorder.enqueue(v); reversePostorder.push(v); }

Strong components algorithms: brief history 1960s: Core OR problem.

・

Widely studied; some practical algorithms.

・

Complexity not understood.

1972: linear-time DFS algorithm (Tarjan).

・

Classic algorithm.

・

Level of difficulty: Algs4++.

・

Demonstrated broad applicability and importance of DFS.

1980s: easy two-pass linear-time algorithm (Kosaraju-Sharir).

・

Forgot notes for lecture; developed algorithm in order to teach it!

・

Later found in Russian scientific literature (1972).

1990s: more easy linear-time algorithms.

・

Gabow: fixed old OR algorithm.

・

Cheriyan-Mehlhorn: needed one-pass algorithm for LEDA.