Exploring Depth-First Search in Algorithms - CMPT 405 Lecture

CMPT 405 Design & Analysis of Algorithms January 17, 2022

General information https://www.cs.sfu.ca/~ishinkar/teaching/spring22/cmpt405/info.html General info Lecture notes Homework assignments

Grading scheme Homeworks: 4 x 15% Final exam: 40% Date TBA All info is on the course homepage

Exploring graphs: Depth First Search

Exploring a tree (Depth First Search) Input: A tree T=(V,E) and a vertex v Goal: visit all vertices of T reachable from v Explore(T, root) 1. pre_visit(root) // e.g. print( visited root) 2. for each child of u, i.e., every edge (root,u) do 2.1 Explore (T, u) 3. post_visit(root) // e.g. print( done with root)

(Depth First Search) 1 /20 a / 9 2 b /13 10 /19 14 /8 3 d e f 17/18 c h i h g / 5 15/16 11 /12 6 / 7 4 previsit postvisit Explore(G,a)

Exploring a tree Input: A tree T=(V,E) and a vertex v Goal: visit all vertices of T reachable from v Explore(T, root) 1. pre_visit(root) // e.g. print( visited root) 2. for each child of u, i.e., every edge (root,u) do 2.1 Explore (T, u) 3. post_visit(root) // e.g. print( done with root) Q: What is the runtime of the algorithm? What about traversing a general graph?

Depth First Search (DFS) Create clock starting with 0. Input: A graph G=(V,E) and a vertex v Goal: explore all vertices reachable from v Explore(G, v) pre_visit(v): clock++ v.pre = clock 1. set v.visited=true 2. pre_visit(v) // e.g. print(first time in v) 3. for all neighbours u of v do post_visit(v): 3.1 If u.visited = false Explore (G, u) post_visit(v) // e.g. print(done with v) clock++ v.post = clock 4.

Depth First Search (DFS) 1 /16 a a /15 /11 2 10 b c b c 6 /9 3 /14 d e f d e f 5 /12 g h 7 /8 g h 4 / 13 previsit postvisit Explore(G,a) DFS tree

Depth First Search (DFS) Create clock starting with 0. Input: A graph G=(V,E) and a vertex v Goal: explore all vertices reachable from v pre_visit(v): DFS(G, v) clock++ v.pre = clock 1. set v.visited=true 2. pre_visit(v) // e.g. print(first time in v) post_visit(v): clock++ v.post = clock 3. for all neighbours u of v do 3.1 If u.visited = false DFS(G, u) u.parent = v post_visit(v) // e.g. print(done with v) Q: What is the runtime of the algorithm? 4. A: O(|V|+|E|) because we visit each edge exactly tiwce (and each vertex v is visited deg(v) times)

DFS finding connected components Input: An undirected graph G=(V,E) Goal: find all connected components of G DFS.pre-visit(): set v.CC=C 1. For all vertices v set v.visited = false set v.CC = 0 // v.CC=5: v belongs to the 5th connected component 2. C = 1; // counter for connected components 3. For all vertices v if v.visited = false c p q r b d DFS(G,v,C) C = C+1 s t a f e g

Directed Acyclic Graphs and Topological Sorting

Directed Acyclic Graphs (DAG) See the Princeton slides by Kevin Wayne https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/03Graphs.pdf

Directed Acyclic Graphs (DAG) 2 6 4 1 5 8 3 7 A directed graph is called acyclic if it contains no directed cycles, i.e., no paths that start and end at the same vertex Topological sorting of a direct acyclic graph G=(V,E) is an ordering of the vertices v1,v2 vn such that for every edge (vi,vj) E it holds that i<j.

Directed Acyclic Graphs (DAG) 0 2 6 1 5 4 8 3 7 Topological order/sorting of a DAG G=(V,E) is an ordering of the vertices v1,v2 vn such that for every edge (vi,vj) E it holds that i<j. 2 5 7 8 4 3 6 1 0

Directed Acyclic Graphs (DAG) 0 2 6 1 5 4 8 3 7 HW: given a DAG G, how many topological sortings of G are there? Compute the number using an algorithm. 2 5 7 8 4 3 6 1 0

Finding a topologic order of a DAG Input: A graph G=(V,E) Goal: find a topological order of G 1. For every vertex v of G set v.visited=false 2. For every vertex v ` 2.1 If v.visited == false run DFS(G,v) 3. Sort v according to v.post in the decreasing order 4. This order is a topological sorting of G

Directed Acyclic Graphs (DAG) 1/12 2/11 4/7 0 3/10 2 6 5/6 17/18 1 5 4 8 13/16 3 7 8/9 14/15 We ran DFS from: 0 ,1, 5 0 2 7 8 4 3 6 5 1

Finding a topologic order of a DAG Input: A graph G=(V,E) 1. For every vertex v of G 2. If v.visited == false 2.1 run DFS(G,v) Sort v according to v.post in the decreasing order 3. Runnig time: Clearly each edge is traversed exactly once. Therefore, if the graph is given as adjacency list representation, then the total running time is O(m+n), where n = |V| and m = |E|.

Finding a topologic order of a DAG Input: A graph G=(V,E) 1. For every vertex v of G Ex: Show that v.pre does not necessarily give a topological order 2. If v.visited == false 2.1 run DFS(G,v) 3. Sort v according to v.post in the decreasing order Key observation: if (v->u) E, then v.post>u.post Proof: two cases if v is explored after u in a separate DFS call, then v.post>u.post Otherwise, DFS must first explore v, then is explores u (as a out- neighbour of v), and only after u is finished, we return to v and set v.post.

Topologic ordering of a DAG (Kahn s algorithm) Here is a different algorithm for finding a topologic sorting of G Idea: If G is a DAG, then it must have vertices with in-degree = 0. These vertices can be put first in the topological order. Then, we can remove them from G, and proceed in the remaining graph (which is algo a DAG) Q: What is the runtime of the algorithm? That is, we maintain a list (linked list) with the topological sorting. In each step we remove a vertex of degree 0 from G and add it to the end of the list

Example 0 2 6 1 5 4 8 3 7 0 2 6 1 5 4 8 3 7 2 5 4 7 8 1 3 6 0

Topologic ordering of a DAG (Kahn s algorithm) Here is a different algorithm for finding a topologic sorting of G Idea: If G is a DAG, then it must have vertices with in-degree = 0. These vertices can be put first in the topological order. Then, we can remove them from G, and proceed n the remaining graph (which is algo a DAG) Q: What is the runtime of the algorithm? Naively: N+(N-1)+(N-2) because in each iteration we search for a source in the remaining graph That is, we maintain a list (linked list) with the topological sorting. Q: Can we do it in O(V+E)? In each step we remove a vertex of degree 0 from G and add it to the end of the list

Kahns algorithm - implementation Input: A graph G=(V,E) 1. L = empty list, will contain a topological sorting of G (e.g. linked list) 2. S = all vertices of in-degree 0 // can be computed in O(|V|+|E|) time 3. For each vertex v, let v.deg = in-degree of v 4. While S is not empty Total running time of the while loop: O(|V|+|E|) 4.1 take v from S 4.2 add v to the end of L 4.3 for each (v->u) E 4.2.1 u.deg-- 4.2.2 if u.deg==0 add u to S Total running time: O(n+m) where n=|V|, m=|E|

Strongly Connected Components of a Directed Graph

Strongly connected components Let G=(V,E) be a directed graph. Two vertices u,v are connected if there a path from u to v and from v to u. Equivalently there is a cycle containing both u and v. A directed graph is said to be strongly connected if there is a path from any vertex to any other vertex. A set W of vertices is a strongly connected component if it is a maximal subset of the vertices such that any two of them are connected. Observation: strongly connected components define a partition of the vertices (no two SCCs intersect).

Strongly connected components Let G=(V,E) be a directed graph. The meta-graph of G is the directed graph of strongly connected components. Observation: the meta-graph is a DAG

Directed Acyclic Graphs (DAG) Recall: in a DFS for a DAG. For every edge v->u we have v.post > u.post Sorting the vertices according to their post number in decreasing order gives a topological order. Observation: For every edge v->u, but no path from u to v, then we have v.post > u.post this holds in any graph. Not necessarily DAG

Finding Strongly Connected Components Let G=(V,E) be a directed graph. The meta-graph of G is the directed graph of strongly connected components. B Observation: the meta-graph is a DAG A D B C A D E C E

Finding strongly connected components Input: A directed graph G=(V,E) B Output: All strongly connected components of G. A Intuition: Suppose we could find a vertex D v in the source of the SCC of G. C B A Then, we can consider GR D E the graph with the edges reversed, C and find all vertices reachable from v. E

Finding strongly connected components Input: A directed graph G=(V,E) Output: All strongly connected components of G. GR the graph G with all edges reversed Algorithm(G) 1. Run DFS on G, and sort the vertices by their post number 2. Take v with the highest post number Find all vertices reachable from v in GR by running DFS(GR,v) Call these CC(v) These together are the source SCC in the meta graph 3. Remove CC(v) from G, and return to step 2

Finding strongly connected components Input: A directed graph G=(V,E) B Output: All strongly connected components of G. A B A D C D C E E

Finding strongly connected components Algorithm(G) 1. Run DFS on G, and sort the vertices by their post number 2. Take v0 with the highest post number Find all vertices reachable from v0 in GR by running DFS(GR,v0) Call these CC(v0) These together are the source SCC in the meta graph 3. Remove CC(v0) from G, and return to step 2 Correctness: Consider the list of vertices sorted by v.post in the reverse order Recall: if (v->u) E but v not reachable from u, then v.post>u.post. Therefore v0 belongs to a source SCC of the meta graph, DFS(GR,v0) can only reach the vertices in the SCC of v0.

Finding strongly connected components Algorithm(G) 1. Run DFS on G, and sort the vertices by their post number 2. Take v0 with the highest post number Find all vertices reachable from v0 in GR by running DFS(GR,v0) Call these CC(v0) These together are the source SCC in the meta graph 3. Remove CC(v0) from G and GR, and return to step 2 Running time : essentially running DFS twice, once on G and once of GR, and hence the total running time is O(|V| + |E|). The DFS on GR has several calls, but each essentially runs on one connected component of G

Questions? Comments?