Design and Analysis of Algorithms: Topological Sorting and DFS on Directed Graphs

csce 411 n.w
1 / 26
Embed
Share

Explore the concepts of topological sorting and depth-first search (DFS) on directed graphs in the context of designing and analyzing algorithms. Learn about adjacency matrices, adjacency lists, running time complexities, and how to order vertices in a directed graph for efficient processing.

  • Algorithms
  • Topological Sorting
  • DFS
  • Directed Graphs
  • Analysis
rayaanacharya
hash_r Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. CSCE-411 Design and Analysis of Algorithms Spring 2025 Instructor: Jianer Chen Office: PETR 428 Phone: 845-4259 Email: chen@cse.tamu.edu Notes 17: Topological sorting

  2. DFS on Directed Graphs 0 0 0 0 0 The adjacency matrix of a directed graph has value ai,j = 1 if [i, j] is an arc in the graph; 0 otherwise. For a weighted graph, ai,j = wi,j is the weight of the arc [i, j]. 1 0 1 0 1 A = 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 adjacency matrix Adj 1 The adjacency list of a directed graph G = (V,E) is an array Adj[1..|V|] of lists, where Adj[v] is a list of all arcs form v. 2 1 5 3 3 4 5 5 3 2 adjacency list For graphs with n nodes and m arcs, adjacency matrices take (n2) space and adjacency list takes (m) space. 1 Check if [v, w] is an arc Adjacency Matrix: O(1) time Adjacency Matrix: O(n) time Adjacency List: O(deg(v)) time Adjacency List: O(1) per edge Traverse all arcs from a vertex v: 3 2 5 4 Notes 15: DFS on Directed Graphs

  3. DFS on Directed Graphs DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w); 3. color[v] = black. 1 8 5 6 main() 1. for (each vertex v) color[v] = white; 2. for (each vertex v) if (color[v] == white) DFS(v). 2 3 7 4 9 Running Time = O(m + n). DFS(1) DFS(4) 4 1 DFS(3) 3 8 DFS(8) 5 DFS(5) DFS(7) 9 7 6 DFS(6) DFS(9) 2 DFS(2) Notes 15: DFS on Directed Graphs

  4. DFS on Directed Graphs DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w); 3. color[v] = black. main() 1. for (each vertex v) color[v] = white; 2. for (each vertex v) if (color[v] == white) DFS(v). Running Time = O(m + n). Topological Sorting Given a directed graph G, order the vertices of G into an array T[1..n] such that if [T[i], T[j]] is an arc, then i < j, or report no such an order exists. Notes 15: DFS on Directed Graphs

  5. DFS on Directed Graphs DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w); 3. color[v] = black. v1 v8 v5 v6 main() 1. for (each vertex v) color[v] = white; 2. for (each vertex v) if (color[v] == white) DFS(v). v4 v2 v3 v7 v9 Running Time = O(m + n). Topological Sorting Given a directed graph G, order the vertices of G into an array T[1..n] such that if [T[i], T[j]] is an arc, then i < j, or report no such an order exists. v4 v9 v6 v8 v5 v7 v1 v3 v2 T[1..9] v4 v9 v6 v2 v1 v8 v5 v3 v7 Notes 15: DFS on Directed Graphs

  6. DFS on Directed Graphs DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w); 3. color[v] = black. DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w) else if (color[w] == gray) Stop ( no topological order ); 3. color[v] = black; T[t] = v; t = t - 1. main() 1. for (each vertex v) color[v] = white; 2. for (each vertex v) if (color[v] == white) DFS(v). T-Sort() \\ T[1..n] is the output array 1. for (each vertex v) color[v] = white; 2. t = n; 3. for (each vertex v) if (color[v] == white) DFS(v). Running Time = O(m + n). Topological Sorting Given a directed graph G, order the vertices of G into an array T[1..n] such that if [T[i], T[j]] is an arc, then i < j, or report no such an order exists. Notes 15: DFS on Directed Graphs

  7. DFS on Directed Graphs Running Time O(m + n). DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w); 3. color[v] = black. DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w) else if (color[w] == gray) Stop ( no topological order ); 3. color[v] = black; T[t] = v; t = t - 1. main() 1. for (each vertex v) color[v] = white; 2. for (each vertex v) if (color[v] == white) DFS(v). T-Sort() \\ T[1..n] is the output array 1. for (each vertex v) color[v] = white; 2. t = n; 3. for (each vertex v) if (color[v] == white) DFS(v). Running Time = O(m + n). Topological Sorting Given a directed graph G, order the vertices of G into an array T[1..n] such that if [T[i], T[j]] is an arc, then i < j, or report no such an order exists. Notes 15: DFS on Directed Graphs

  8. DFS on Directed Graphs Running Time O(m + n). DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w); 3. color[v] = black. DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w) else if (color[w] == gray) Stop ( no topological order ); 3. color[v] = black; T[t] = v; t = t - 1. main() 1. for (each vertex v) color[v] = white; 2. for (each vertex v) if (color[v] == white) DFS(v). T-Sort() \\ T[1..n] is the output array 1. for (each vertex v) color[v] = white; 2. t = n; 3. for (each vertex v) if (color[v] == white) DFS(v). Running Time = O(m + n). Topological Sorting Given a directed graph G, order the vertices of G into an array T[1..n] such that if [T[i], T[j]] is an arc, then i < j, or report no such an order exists. Why does this algorithm work? Notes 15: DFS on Directed Graphs

  9. DFS on Directed Graphs Running Time O(m + n). DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w); 3. color[v] = black. DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w) else if (color[w] == gray) Stop ( no topological order ); 3. color[v] = black; T[t] = v; t = t - 1. main() 1. for (each vertex v) color[v] = white; 2. for (each vertex v) if (color[v] == white) DFS(v). T-Sort() \\ T[1..n] is the output array 1. for (each vertex v) color[v] = white; 2. t = n; 3. for (each vertex v) if (color[v] == white) DFS(v). Running Time = O(m + n). Topological Sorting Given a directed graph G, order the vertices of G into an array T[1..n] such that if [T[i], T[j]] is an arc, then i < j, or report no such an order exists. Why does this algorithm work? 1. Vertices are placed in T[1..n] (backwards) when they become black. Notes 15: DFS on Directed Graphs

  10. DFS on Directed Graphs Running Time O(m + n). DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w); 3. color[v] = black. DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w) else if (color[w] == gray) Stop ( no topological order ); 3. color[v] = black; T[t] = v; t = t - 1. main() 1. for (each vertex v) color[v] = white; 2. for (each vertex v) if (color[v] == white) DFS(v). T-Sort() \\ T[1..n] is the output array 1. for (each vertex v) color[v] = white; 2. t = n; 3. for (each vertex v) if (color[v] == white) DFS(v). Running Time = O(m + n). Topological Sorting Given a directed graph G, order the vertices of G into an array T[1..n] such that if [T[i], T[j]] is an arc, then i < j, or report no such an order exists. Why does this algorithm work? 1. Vertices are placed in T[1..n] (backwards) when they become black. 2. Take any arc [v, w]. When DFS(v) checks the arc [v, w], what is w s color? Notes 15: DFS on Directed Graphs

  11. DFS on Directed Graphs Running Time O(m + n). DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w); 3. color[v] = black. DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w) else if (color[w] == gray) Stop ( no topological order ); 3. color[v] = black; T[t] = v; t = t - 1. main() 1. for (each vertex v) color[v] = white; 2. for (each vertex v) if (color[v] == white) DFS(v). T-Sort() \\ T[1..n] is the output array 1. for (each vertex v) color[v] = white; 2. t = n; 3. for (each vertex v) if (color[v] == white) DFS(v). Running Time = O(m + n). Topological Sorting Given a directed graph G, order the vertices of G into an array T[1..n] such that if [T[i], T[j]] is an arc, then i < j, or report no such an order exists. Why does this algorithm work? 1. Vertices are placed in T[1..n] (backwards) when they become black. 2. Take any arc [v, w]. When DFS(v) checks the arc [v, w], what is w s color? 2.1 w is while: then DFS(w) is called, and DFS(w) finishes before DFS(v), so w is placed on the right of v in T[1..n]. Notes 15: DFS on Directed Graphs

  12. DFS on Directed Graphs Running Time O(m + n). DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w); 3. color[v] = black. DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w) else if (color[w] == gray) Stop ( no topological order ); 3. color[v] = black; T[t] = v; t = t - 1. main() 1. for (each vertex v) color[v] = white; 2. for (each vertex v) if (color[v] == white) DFS(v). T-Sort() \\ T[1..n] is the output array 1. for (each vertex v) color[v] = white; 2. t = n; 3. for (each vertex v) if (color[v] == white) DFS(v). Running Time = O(m + n). Topological Sorting Given a directed graph G, order the vertices of G into an array T[1..n] such that if [T[i], T[j]] is an arc, then i < j, or report no such an order exists. Why does this algorithm work? 1. Vertices are placed in T[1..n] (backwards) when they become black. 2. Take any arc [v, w]. When DFS(v) checks the arc [v, w], what is w s color? 2.1 w is while: then DFS(w) is called, and DFS(w) finishes before DFS(v), so w is placed on the right of v in T[1..n]. 2.2 w is black: then w is already in T[1..n] before DFS(v) finishes, so w is placed on the right of v in T[1..n]. Notes 15: DFS on Directed Graphs

  13. DFS on Directed Graphs Running Time O(m + n). DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w); 3. color[v] = black. DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w) else if (color[w] == gray) Stop ( no topological order ); 3. color[v] = black; T[t] = v; t = t - 1. main() 1. for (each vertex v) color[v] = white; 2. for (each vertex v) if (color[v] == white) DFS(v). T-Sort() \\ T[1..n] is the output array 1. for (each vertex v) color[v] = white; 2. t = n; 3. for (each vertex v) if (color[v] == white) DFS(v). Running Time = O(m + n). Topological Sorting Given a directed graph G, order the vertices of G into an array T[1..n] such that if [T[i], T[j]] is an arc, then i < j, or report no such an order exists. Why does this algorithm work? 1. Vertices are placed in T[1..n] (backwards) when they become black. 2. Take any arc [v, w]. When DFS(v) checks the arc [v, w], what is w s color? 2.1 w is while: then DFS(w) is called, and DFS(w) finishes before DFS(v), so w is placed on the right of v in T[1..n]. 2.2 w is black: then w is already in T[1..n] before DFS(v) finishes, so w is placed on the right of v in T[1..n]. 2.3 w is gray: then w is an ancestor of v in the DFS tree, so the tree path from w to v plus the arc [v, w] makes a cycle: topological sorting is impossible. Notes 15: DFS on Directed Graphs

  14. DFS on Directed Graphs Strongly Connected Components. Definition. Let G be a directed graph. Two vertices v and w in G are in the same strongly connected component (scc) if in the graph G, there exist a (directed) path from v to w and a (directed) path from w to v. Notes 17: Strongly Connected Components

  15. DFS on Directed Graphs Strongly Connected Components. Definition. Let G be a directed graph. Two vertices v and w in G are in the same strongly connected component (scc) if in the graph G, there exist a (directed) path from v to w and a (directed) path from w to v. Notes 17: Strongly Connected Components

  16. DFS on Directed Graphs Strongly Connected Components. Definition. Let G be a directed graph. Two vertices v and w in G are in the same strongly connected component (scc) if in the graph G, there exist a (directed) path from v to w and a (directed) path from w to v. Observation. Scc s partition the graph vertices. Problem (SCC). Given a directed graph G, find all scc s in G (i.e., label the vertices so vertices in the same scc get the same label). Notes 17: Strongly Connected Components

  17. DFS on Directed Graphs Problem (SCC). Given a directed graph G, find all scc s in G. 4 9 2 8 3 7 6 5 1 Notes 18: Strongly Connected Components II

  18. DFS on Directed Graphs Problem (SCC). Given a directed graph G, find all scc s in G. DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w) 3. color[v] = black. main() 1. for (each vertex v) color[v] = white; 2. for (each vertex v) if (color[v] == white) DFS(v). 4 9 2 8 3 7 6 5 1 Notes 18: Strongly Connected Components II

  19. DFS on Directed Graphs Problem (SCC). Given a directed graph G, find all scc s in G. DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w) 3. color[v] = black. main() 1. for (each vertex v) color[v] = white; 2. for (each vertex v) if (color[v] == white) DFS(v). 1 2 4 7 9 2 8 4 6 3 9 7 6 5 5 8 1 3 Notes 18: Strongly Connected Components II

  20. DFS on Directed Graphs Problem (SCC). Given a directed graph G, find all scc s in G. DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w) 3. color[v] = black. main() 1. for (each vertex v) color[v] = white; 2. for (each vertex v) if (color[v] == white) DFS(v). 1 2 4 7 9 2 8 4 6 3 9 7 6 5 5 8 1 3 Notes 18: Strongly Connected Components II

  21. DFS on Directed Graphs Problem (SCC). Given a directed graph G, find all scc s in G. DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w) 3. color[v] = black. main() 1. for (each vertex v) color[v] = white; 2. for (each vertex v) if (color[v] == white) DFS(v). 1 2 4 7 9 2 8 4 6 3 9 7 6 5 5 8 1 3 Notes 18: Strongly Connected Components II

  22. DFS on Directed Graphs Problem (SCC). Given a directed graph G, find all scc s in G. DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w) 3. color[v] = black. main() 1. for (each vertex v) color[v] = white; 2. for (each vertex v) if (color[v] == white) DFS(v). 1 2 4 7 9 2 8 4 6 3 9 7 6 5 5 8 1 3 Notes 18: Strongly Connected Components II

  23. DFS on Directed Graphs Problem (SCC). Given a directed graph G, find all scc s in G. DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w) 3. color[v] = black; T[t] = v; t = t - 1. main() \\ T[1..n] is an array 1. for (each vertex v) color[v] = white; 2. t = n; 3. for (each vertex v) if (color[v] == white) DFS(v). Notes 18: Strongly Connected Components II

  24. DFS on Directed Graphs Problem (SCC). Given a directed graph G, find all scc s in G. DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w) 3. color[v] = black; T[t] = v; t = t - 1. main() \\ T[1..n] is an array 1. for (each vertex v) color[v] = white; 2. t = n; 3. for (each vertex v) if (color[v] == white) DFS(v). What is T[1] after step 3 of the main algorithm? ? T Notes 18: Strongly Connected Components II

  25. DFS on Directed Graphs Problem (SCC). Given a directed graph G, find all scc s in G. DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w) 3. color[v] = black; T[t] = v; t = t - 1. a d r main() \\ T[1..n] is an array 1. for (each vertex v) color[v] = white; 2. t = n; 3. for (each vertex v) if (color[v] == white) DFS(v). c b s t What is T[1] after step 3 of the main algorithm? ? T Notes 18: Strongly Connected Components II

  26. DFS on Directed Graphs Problem (SCC). Given a directed graph G, find all scc s in G. DFS(v) 1. color[v] = gray; 2. for (each arc [v, w]) if (color[w] == white) DFS(w) 3. color[v] = black; T[t] = v; t = t - 1. r main() \\ T[1..n] is an array 1. for (each vertex v) color[v] = white; 2. t = n; 3. for (each vertex v) if (color[v] == white) DFS(v). What is T[1] after step 3 of the main algorithm? r T Notes 18: Strongly Connected Components II

Related


No related presentations.

More Related Content