This post is based on Chapter 22, <<Introduction to Algorithms>>, Third Edition.

BFS(G,s): for each vertex u in G.V - {s}: u.color = white u.d = infinity u.previous = NIL s.color = gray s.d = 0 s.previous = NIL Q = a new queue ENQUEUE(Q,s) while Q is not empty: u = DEQUEUE(Q) for each v in G.Adj[u]: if v.color == white: v.color = gray v.d = u.d + 1 v.previous = u ENQUEUE(Q,v) u.color = black

- Running time of BFS: O(V+E)
- print out the path from s to v

Print-path(G,s,v): if v==s: print s else if v.previous == NIL: print "no path from s to v exists" else: Print-path(G,s,v.previous) print v

- DFS

DFS(G,s): for each vertex u in G.V: u.color = white u.previous = NIL time = 0 for each vertex u in G.V: //ensure that all of the vertices are visited if u.color == white: DFS-VISIT(G,u) DFS-VISIT(G,u): time = time + 1 //every time we update the time attribute of a node, we increment it by 1 u.d = time u.color = gray for each v in G.Adj[u]: if v.color == white: v.previous = u DFS-VISIT(G,v) // Note the use of recursion in DFS; or we can use a stack to implement DFS-VISIT u.color = black time = time + 1 //every time we update the time attribute of a node, we increment it by 1 u.f = time

- Running time: O(V+E)

**Parenthesis theorem**: in any directed or undirected graph G(V, E) that has been DFS visited, any pair of vertices u and v satisfy that:

- [u.d, u.f] and [v.d, v.f] do not overlap at all
- one time frame of [u.d, u.f] and [v.d, v.f] is completed included in the other time frame

**White-path theorem: **In a directed or undirected graph G = (V, E)’s depth-first forests, vertice v is the cild of u if and only if there exists a path that is composed of all white vertices when u is just discovered.

**Classification of edges of DFS:**

- tree edge: the edge in the depth-first forest.
- backward edge: the edge that connects u to its “previous” vertice v. (Acyclic graph has no backward edges)
- forward edge: the edge that connects u to its child vertice v.
- cross edge: other edges. Can be an edge that connects two vertices in one depth-first tree or the one that connects two vertices in two different depth-first trees

**During the process of DFS, for the edge (u,v):**

- if v is white, then (u,v) is a tree edge
- if v is gray, then (u,v) is a backward edge
- if v is black, then (u,v) is a forward edge or cross edge

**Theorem**: during the DFS in a **undirected graph G**, there can only exist tree edges and backward edges.

**Topological Sort: only for directed acyclic graph**

TOPOLOGICAL-SORT(G): call DFS(G) to compute finishing time v.f for each vertex v as each vertex is finished, insert it onto the front of a linked list return the linked list of vertices

**Strongly connected component**: see chapter 23 of the book