Algorithms for Graph Traversal and Analysis
Learn about the efficient algorithms for traversing and analyzing graphs using techniques like Depth-First Search (DFS) and Breadth-First Search (BFS). Understand their applications in determining graph connectivity, detecting cycles, finding paths, and testing bipartiteness. Explore how DFS and BFS are instrumental in solving diverse graph-related problems.
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.
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
CSCE-411 Design and Analysis of Algorithms Spring 2025 Instructor: Jianer Chen Office: PETR 428 Phone: 845-4259 Email: chen@cse.tamu.edu Notes 16: Algorithms on directed graphs
Traversing a Graph Both DFS and BFS run in time O(m+n). Two basic methods: Breadth-First-Search and Depth-First-Search Breadth-First-Search Depth-First-Search BFS(s) \\ Q is a queue 1. color[s] = gray; Q s; 2. while (Q is not empty) Q w; for (each edge [w, v]) if (color[v] == white) color[v] = gray; Q v; color[w] = black. DFS(v) 1. color[v] = gray; 2. for (each edge [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). Main() 1. for (each vertex v) color[v] = white; 2. for (each vertex v) if (color[v] == white) BFS(v). Based on BFS and DFS, we can (1) test if a graph is connected; (2) test if a graph contains a cycle; (3) test if a graph is a tree; (4) find a shortest path in a graph (BFS); (5) test if a graph is bipartite; and (6) do many other things. Notes 15: Applications of DFS and BFS
Traversing a Graph Both DFS and BFS run in time O(m+n). Two basic methods: Breadth-First-Search and Depth-First-Search Breadth-First-Search Depth-First-Search BFS(s) \\ Q is a queue 1. color[s] = gray; Q s; 2. while (Q is not empty) Q w; for (each edge [w, v]) if (color[v] == white) color[v] = gray; Q v; color[w] = black. DFS(v) 1. color[v] = gray; 2. for (each edge [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). Main() 1. for (each vertex v) color[v] = white; 2. for (each vertex v) if (color[v] == white) BFS(v). (5) test if a graph is bipartite Definition. A graph G = (V, E) is bipartite if its vertex set V can be partitioned into two disjoint subsets V = L R, L R = , such that every edge in G has one end in L and one end in R. In other words, the graph is 2-colorable. R L Notes 15: Applications of DFS and BFS
Traversing a Graph Both DFS and BFS run in time O(m+n). Two basic methods: Breadth-First-Search and Depth-First-Search DFS-Bipartiteness Depth-First-Search DFS(v) 1. color[v] = gray; 2. for (each edge [v, w]) if (color[w] == white) if (side[v]==L) then side[w] = R else side[w] = L; DFS(w); else if (side[v]==side[w]) return( not bipartite ); 3. color[v] = black. DFS(v) 1. color[v] = gray; 2. for (each edge [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). main() 1. for (each vertex v) color[v] = white; 2. for (each vertex v) if (color[v] == white) side[v] = L; DFS(v); 3. return( bipartite ). R L (5) test if a graph is bipartite Definition. A graph G = (V, E) is bipartite if its vertex set V can be partitioned into two disjoint subsets V = L R, L R = , such that every edge in G has one end in L and one end in R. In other words, the graph is 2-colorable. Notes 15: Applications of DFS and BFS
Connected Components Definition. Let G be an undirected graph. A connected component (CC) of G is a maximal subgraph that is connected. Notes 15: DFS on Directed Graphs
Connected Components Definition. Let G be an undirected graph. A connected component (CC) of G is a maximal subgraph that is connected. Problem [Connected-Components]: Given an undirected graph G, find all connected components of G (i.e., label all vertices so that vertices in the same CC have the same label. Notes 15: DFS on Directed Graphs
Connected Components Definition. Let G be an undirected graph. A connected component (CC) of G is a maximal subgraph that is connected. Problem [Connected-Components]: Given an undirected graph G, find all connected components of G (i.e., label all vertices so that vertices in the same CC have the same label. Both DFS and BFS can be used to solve the CC problem and both run in time O(n+m). Notes 15: DFS on Directed Graphs
Connected Components Definition. Let G be an undirected graph. A connected component (CC) of G is a maximal subgraph that is connected. Problem [Connected-Components]: Given an undirected graph G, find all connected components of G (i.e., label all vertices so that vertices in the same CC have the same label. Both DFS and BFS can be used to solve the CC problem and both run in time O(n+m). Depth-First-Search DFS(v) 1. color[v] = gray; 2. for (each edge [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). Notes 15: DFS on Directed Graphs
Connected Components Definition. Let G be an undirected graph. A connected component (CC) of G is a maximal subgraph that is connected. Problem [Connected-Components]: Given an undirected graph G, find all connected components of G (i.e., label all vertices so that vertices in the same CC have the same label. Both DFS and BFS can be used to solve the CC problem and both run in time O(n+m). CC-Algorithm (DFS-version) DFS(v) 1. color[v] = gray; CC[v] = cc#; 2. for (each edge [v, w]) if (color[w] == white) DFS(w); 3. color[v] = black. Depth-First-Search DFS(v) 1. color[v] = gray; 2. for (each edge [v, w]) if (color[w] == white) DFS(w); 3. color[v] = black. main() 1. for (each vertex v) color[v] = white; 2. cc# = 0; 3. for (each vertex v) if (color[v] == white) cc# = cc# + 1; DFS(v); 4. output(CC[1..n]). main() 1. for (each vertex v) color[v] = white; 2. for (each vertex v) if (color[v] == white) DFS(v). Notes 15: DFS on Directed Graphs
DFS on Directed Graphs Notes 15: DFS on Directed Graphs
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 1 3 2 5 4 Notes 15: DFS on Directed Graphs
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
DFS on Directed Graphs DFS(v) 1. color[v] = gray; 2. for (each edge [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). Notes 15: DFS on Directed Graphs
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). Notes 15: DFS on Directed Graphs
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). Notes 15: DFS on Directed Graphs
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
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
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
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. Notes 15: DFS on Directed Graphs
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] Notes 15: DFS on Directed Graphs
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
