Depth First Search (DFS) Algorithm

• The text describes the Design and Analysis of Algorithms, Lecture 16, covering Depth First Search (DFS) and Topological Sort.
• Breadth-first search starts at any vertex of the graph.

Spanning Tree

• If the graph is connected, n-1 edges used to reach unvisited vertices define a spanning tree (breadth-first spanning tree).
• Time complexity is O(n²) when an adjacency matrix is used.
• Time complexity is O(n+e) when adjacency lists are used, where e is the number of edges.

Depth-First Search (DFS) Algorithm

• Utilizes colors (WHITE, GRAY, BLACK) to track vertex states during traversal.
• Pseudocode outline:
  • For each vertex u in the graph G, initialize color[u] to WHITE and π[u] to NIL.
  • Set the initial time to 0.
  • For each vertex u in G, if color[u] is WHITE, call DFS-VISIT(u).

DFS-VISIT(u) Function Details

• color[u] is set to GRAY upon discovery of vertex u.
• Time is incremented, and d[u] (discovery time) is assigned the current time.
• For each adjacent vertex v of u, explore the edge (u, v).
  • If color[v] is WHITE, set π[v] to u and recursively call DFS-VISIT(v).
• After exploring all adjacent vertices, color[u] is set to BLACK, indicating it is finished.
• The finishing time f[u] is recorded.

DFS Execution Example

• Starting the search at vertex 1

• Vertex 1 is labeled (d[1]=1), with a depth-first search from either vertex 2 or 4 being conducted, and vertex 2 is selected

• Vertex 2 is labeled (d[2]=2), with a depth-first search continuing now from from either vertex 3, 5, or 6.

• Vertex 5 is labeled (d[5]=3), with a depth-first search continuing now from from either vertex 3, 7, or 9.

• Vertex 9 is then labeled (d[9]=4), with a depth-first search continuing from vertex 6 or 8.

• Vertex 8 gets labeled, returns to 9, then a dfs(6) occurs.

• Vertex 6 gets labeled, a depth first search occurs from vertices 4 or 7

• Vertex 4 is labelled as gray, before returning to 6, and a dfs(7) occurs

• Then vertex 7 gets labelled, before a return to 6 and then to 9

• The algorithm then returns to 5

• A defs(3) then occurs

• Vertex 3 gets labelled, before a return to 5 and then to 2

• There is then a return to 1

• The example walks through labeling/finishing vertices 10 and 11.

DFS Properties

• It has the same complexity as Breadth-First Search (BFS).
• It shares the same properties with BFS regarding path finding, connected components, and spanning trees.
• The edges used to reach unlabeled vertices define a depth-first spanning tree when the graph is connected.
• Some problems are better suited for BFS, while others are better handled by DFS.

Parenthesis Theorem

• For any two vertices u and v, exactly one of the following three conditions holds

• The intervals [d[u], f[u]] and [d[v], f[v]] are entirely disjoint and neither is a descendant of the other in depth-first forest.

• The interval [d[u], f[u]] is entirely within [d[v], f[v]], making u a descendant of v in the depth-first tree

• The interval [d[v], f[v]] is entirely within [d[u], f[u]], making v a descendant of u in the depth-first tree

Nesting of Descendants' Intervals

• Vertex v is a proper descendant of vertex u in the depth-first search forest for a directed or undirected graph G if and only if d[u] < d[v] < f[v] < f[u]

White-Path Theorem

• In a DFS forest of a direxted / undirected graph G = (V, E), vertex v is a descendant of vertex u if and only if at the time d[u], the search discovers vertex u, vertex v can be reached from vertex u along a path on all white vertices

Directed Graphs (Digraphs)

• Digraphs are graphs whose edges are all directed.
• "Digraph" is simply short for "directed graph."
• An application is Scheduling, where, for example, edge (A, B) specifies that task A must be completed before task B can commence.

Edges

• Tree edges are edges within the depth-first forest Gπ; edge (u, v) is a tree edge if v was first discovered when exploring edge (u, v).
• Back edges connect a vertex u to an ancestor v in a depth-first tree. Self-loops in directed graphs are considered back edges.
• Forward edges are non-tree edges connecting a vertex u to a descendant v in the depth-first tree.
• Cross edges are all other edges that go between vertices in the same depth-first tree where one vertex is not an ancestor of the other, or between vertices in different depth-first trees.

Linear Ordering and Topological Sort

• Many problems involve a set of tasks where some must be done before others.
• Topological sort linearly arranges courses in the order they should be taken, considering prerequisites.
• Topological sort arranges vertices in a directed acyclic graph (DAG) as a sequence, such that no vertex appears before its predecessor.
• A Directed Acyclic Graph (DAG) is a digraph without directed cycles.
• A topological ordering of a digraph numbers vertices such that for every edge (vi, vj), i < j.
• A digraph admits a topological ordering if and only if it is a DAG.
• A digraph is a DAG if and only if a DFS yields no back edges.

Topological Sort Algorithm

• Call DFS(G) to compute the finishing time f[v] for each vertex v.
• As each vertex is finished, insert it onto the front of a linked list.
• Return the linked list of vertices.
• The runtime for topological sort is O(V+E).
• DFS takes O(V+E) time, and inserting each of the |V| vertices onto the linked list takes O(1) time.