Transcript Depth First Search Neil Tang 4/1/2010

Depth First Search
Neil Tang
4/1/2010
CS223 Advanced Data Structures and Algorithms
1
Class Overview
 Breadth First Search (BFS)
 Depth First Search (DFS)
 DFS on an undirected graph
 DFS on a digraph
 Strong connected components
CS223 Advanced Data Structures and Algorithms
2
BFS
 Visit the nodes that are one-hop away from the starting
node one by one, then the nodes that are two-hop away,
then …, i.e., layer by layer.
 A queue should be used to implement the BFS.
 Make sure each node is visited exactly once.
CS223 Advanced Data Structures and Algorithms
3
DFS
 A generalized pre-order traversal
Time Complexity: O(|V|+|E|)
CS223 Advanced Data Structures and Algorithms
4
DFS on An Undirected Graph
DFS(A): A,B,C,D,E
CS223 Advanced Data Structures and Algorithms
5
DFS on An Undirected Graph
 DFS can be used to find if an undirected graph is
connected or not.
 DFS can also be used to find all the connected
components.
CS223 Advanced Data Structures and Algorithms
6
DFS on A Digraph
DFS(B): B,C,A,D,E,F;
DFS(H): H,J,I;
DFS(G): G.
CS223 Advanced Data Structures and Algorithms
7
Strongly Connected Components
 Perform DFS until all nodes are visited.
 Construct an auxiliary graph Gr.
 Perform DFS on Gr in the reverse order of the index
numbers.
CS223 Advanced Data Structures and Algorithms
8
Strongly Connected Components
Gr
DFS(G): G;
DFS(H): H,I,J;
DFS(B): B,A,C,F;
The forest after the first DFS
DFS(D): D; DFS(E): E.
Strongly Connected Components: (G), (H,I,J), (B,A,C,F),(D),(E)
CS223 Advanced Data Structures and Algorithms
9