L12 - Graph Algorithms - Traversal.pdf

CP312 Algorithm Design and Analysis I LECTURE 12: GRAPH ALGORITHMS – TRAVERSAL Graph Definitions Review 1 2 3 4 A directed graph (digraph) 𝐺 = (𝑉, 𝐸) is an ordered pair consisting of: ◦ A set 𝑉 = {1, … , 𝑛} of 𝑛 vertices ◦ A set 𝐸 ⊆ 𝑉 × 𝑉 of edges where each edge is an ordered pair of vertices An un...

CP312 Algorithm Design and Analysis I LECTURE 12: GRAPH ALGORITHMS – TRAVERSAL Graph Definitions Review 1 2 3 4 A directed graph (digraph) 𝐺 = (𝑉, 𝐸) is an ordered pair consisting of: ◦ A set 𝑉 = {1, … , 𝑛} of 𝑛 vertices ◦ A set 𝐸 ⊆ 𝑉 × 𝑉 of edges where each edge is an ordered pair of vertices An undirected graph 𝐺 = (𝑉, 𝐸) is an ordered pair consisting of: ◦ A set 𝑉 = {1, … , 𝑛} of 𝑛 vertices ◦ A set 𝐸 ⊆ 𝑉2 of edges where each edge is an unordered pair of vertices A weighted (directed or undirected) graph 𝐺 = (𝑉, 𝐸) is a graph with an associated weight function 𝑤: 𝐸 → ℝ that assigns weights to the edges. Graph Definitions Review See Appendix B in the textbook for the full review A path in a graph is a sequence (𝑣0 , … , 𝑣𝑘 ) of vertices where 𝑣𝑖−1 , 𝑣𝑖 ∈ 𝐸 A cycle in a graph is a path (𝑣0 , … , 𝑣𝑘 ) where 𝑣0 = 𝑣𝑘 A graph is connected if every pair of vertices is connected by a path. A graph is acyclic if it has no cycles. A tree is a connected, acyclic, undirected graph. 1 2 3 4 Graph Definitions Review Examples of Trees: Rooted Tree Free Tree Graph Definitions Review Some properties of Trees: For any tree 𝑇 = (𝑉, 𝐸) ◦ ◦ ◦ ◦ The number of edges 𝐸 = 𝑉 − 1 Any two vertices in a tree are connected by exactly one path. Adding one additional edge to a tree creates exactly one cycle. Every rooted tree with at least two vertices has at least two leaves. Graph Definitions Review 1 2 3 4 Representing digraph 𝐺 = (𝑉, 𝐸): ◦ 𝑉 = 1,2,3,4 ◦ 𝐸 = 1,2 , 1,3 , 4,2 , 3,2 Adjacency matrix representation 0 if 𝑖, 𝑗 ∉ 𝐸 ◦ 𝐴 𝑖, 𝑗 = ቊ 1 if 𝑖, 𝑗 ∈ 𝐸 Adjacency list representation ◦ ∀𝑣 ∈ 𝑉: 𝐴𝑑𝑗 𝑣 = 𝑢 𝑣, 𝑢 ∈ 𝐸} 𝑨 1 2 3 4 1 0 1 1 0 2 0 0 0 0 3 0 1 0 0 4 0 1 0 0 𝐴𝑑𝑗 𝐴𝑑𝑗 𝐴𝑑𝑗 𝐴𝑑𝑗 1 2 3 4 = 2,3 = = 2 = 2 Graph Algorithms Resources Textbook appendix Visual reference to follow alongside your readings: ◦ visualgo.net Graph Traversal A common task in graphs is search or traversal. Traversing the graph means systematically following the edges of the graph so as to visit the vertices of the graph. Traversing is usually performed to discover some of the structure of the graph and is often used as part of other graph algorithms. Graph Traversal Two different traversal algorithms: 1. Breadth-first search 2. Depth-first search Graph Traversal 𝑟 𝑠 𝑡 𝑢 𝑣 𝑤 𝑥 𝑦 Note: The weights of the edges are all equal to 1. The goal is to start on a vertex and visit all vertices. Breadth-First Search Graph is represented as adjacency list Starts with a source vertex 𝑠 then visits all neighbours of 𝑠 then visits all neighbours of the neighbours of 𝑠, etc. ◦ Until we reach all vertices. Computes the number of edges is takes to go from 𝑠 to every reachable vertex. Produces a “breadth-first tree” with root 𝑠 Breadth-First Search BFS(𝑉, 𝐸, 𝑠): for each vertex 𝑣 ∈ 𝑉 − {𝑠} 𝑣. 𝑠𝑡𝑎𝑡𝑒 = 𝑢𝑛𝑣𝑖𝑠𝑖𝑡𝑒𝑑, 𝑣. 𝑑𝑖𝑠𝑡 = ∞, 𝑣. 𝑝𝑟𝑒𝑑 = 𝑛𝑢𝑙𝑙 𝑠. 𝑠𝑡𝑎𝑡𝑒 = 𝑣𝑖𝑠𝑖𝑡𝑒𝑑, 𝑠. 𝑑𝑖𝑠𝑡 = 0, 𝑠. 𝑝𝑟𝑒𝑑 = 𝑛𝑢𝑙𝑙 Set queue 𝑄 = 𝑛𝑢𝑙𝑙 ENQUEUE(𝑄, 𝑠) while 𝑄 ≠ 𝑛𝑢𝑙𝑙 𝑣 = DEQUEUE(𝑄) for each 𝑢 ∈ 𝐴𝑑𝑗[𝑣] if 𝑢. 𝑠𝑡𝑎𝑡𝑒 == 𝑢𝑛𝑣𝑖𝑠𝑖𝑡𝑒𝑑 𝑢. 𝑠𝑡𝑎𝑡𝑒 = 𝑣𝑖𝑠𝑖𝑡𝑒𝑑 𝑢. 𝑑𝑖𝑠𝑡 = 𝑣. 𝑑𝑖𝑠𝑡 + 1 𝑢. 𝑝𝑟𝑒𝑑 = 𝑣 ENQUEUE(𝑄, 𝑢) 𝑣. 𝑠𝑡𝑎𝑡𝑒 = 𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑒 Breadth-First Search: Example 𝑟 𝑠 𝑡 𝑢 ∞ 0 ∞ ∞ Status Unvisited Visited Complete 𝑄 ∞ ∞ ∞ ∞ 𝑣 𝑤 𝑥 𝑦 𝒔 Breadth-First Search: Example 𝑟 𝑠 𝑡 𝑢 ∞ 0 ∞ ∞ Status Unvisited Visited Complete 𝑄 ∞ ∞ ∞ ∞ 𝑣 𝑤 𝑥 𝑦 𝒔 Dequeue Breadth-First Search: Example 𝑟 𝑠 𝑡 𝑢 1 0 ∞ ∞ Status Unvisited Visited Complete Enqueue Enqueue 𝑄 ∞ 1 ∞ ∞ 𝑣 𝑤 𝑥 𝑦 𝒘 𝒓 Breadth-First Search: Example 𝑟 𝑠 𝑡 𝑢 1 0 ∞ ∞ Status Unvisited Visited Complete 𝑄 ∞ 1 ∞ ∞ 𝑣 𝑤 𝑥 𝑦 𝒘 Dequeue 𝒓 Breadth-First Search: Example 𝑟 𝑠 𝑡 𝑢 1 0 2 ∞ Status Unvisited Visited Complete Enqueue Enqueue 𝑄 ∞ 1 2 ∞ 𝑣 𝑤 𝑥 𝑦 𝒓 𝒕 𝒙 Breadth-First Search: Example 𝑟 𝑠 𝑡 𝑢 1 0 2 ∞ Status Unvisited Visited Complete 𝑄 ∞ 1 2 ∞ 𝑣 𝑤 𝑥 𝑦 𝒓 Dequeue 𝒕 𝒙 Breadth-First Search: Example 𝑟 𝑠 𝑡 𝑢 1 0 2 ∞ Status Unvisited Visited Complete Enqueue 𝑄 2 1 2 ∞ 𝑣 𝑤 𝑥 𝑦 𝒕 𝒙 𝒗 Breadth-First Search: Example 𝑟 𝑠 𝑡 𝑢 1 0 2 ∞ Status Unvisited Visited Complete 𝑄 2 1 2 ∞ 𝑣 𝑤 𝑥 𝑦 𝒕 Dequeue 𝒙 𝒗 Breadth-First Search: Example 𝑟 𝑠 𝑡 𝑢 1 0 2 3 Status Unvisited Visited Complete Enqueue 𝑄 2 1 2 ∞ 𝑣 𝑤 𝑥 𝑦 𝒙 𝒗 𝒖 Breadth-First Search: Example 𝑟 𝑠 𝑡 𝑢 1 0 2 3 Status Unvisited Visited Complete 𝑄 2 1 2 ∞ 𝑣 𝑤 𝑥 𝑦 𝒙 Dequeue 𝒗 𝒖 Breadth-First Search: Example 𝑟 𝑠 𝑡 𝑢 1 0 2 3 Status Unvisited Visited Complete Enqueue 𝑄 2 1 2 3 𝑣 𝑤 𝑥 𝑦 𝒗 𝒖 𝒚 Breadth-First Search: Example 𝑟 𝑠 𝑡 𝑢 1 0 2 3 Status Unvisited Visited Complete 𝑄 2 1 2 3 𝑣 𝑤 𝑥 𝑦 𝒗 Dequeue 𝒖 𝒚 Breadth-First Search: Example 𝑟 𝑠 𝑡 𝑢 1 0 2 3 Status Unvisited Visited Complete 𝑄 2 1 2 3 𝑣 𝑤 𝑥 𝑦 𝒖 Dequeue 𝒚 Breadth-First Search: Example 𝑟 𝑠 𝑡 𝑢 1 0 2 3 Status Unvisited Visited Complete 𝑄 2 1 2 3 𝑣 𝑤 𝑥 𝑦 𝒚 Dequeue Breadth-First Search: Example 𝑟 𝑠 𝑡 𝑢 1 0 2 3 Status Unvisited Visited Complete 𝑄 2 1 2 3 𝑣 𝑤 𝑥 𝑦 𝑻 𝒏 = 𝑶(𝑽 + 𝑬) Analysis of Breadth-First Search Θ(|𝑉|) 𝑂(𝐸) BFS(𝑉, 𝐸, 𝑠): for each vertex 𝑣 ∈ 𝑉 − {𝑠} 𝑣. 𝑠𝑡𝑎𝑡𝑒 = 𝑢𝑛𝑣𝑖𝑠𝑖𝑡𝑒𝑑, 𝑣. 𝑑𝑖𝑠𝑡 = ∞, 𝑣. 𝑝𝑟𝑒𝑑 = 𝑛𝑢𝑙𝑙 𝑠. 𝑠𝑡𝑎𝑡𝑒 = 𝑣𝑖𝑠𝑖𝑡𝑒𝑑, 𝑠. 𝑑𝑖𝑠𝑡 = 0, 𝑠. 𝑝𝑟𝑒𝑑 = 𝑛𝑢𝑙𝑙 Set queue 𝑄 = 𝑛𝑢𝑙𝑙 ENQUEUE(𝑄, 𝑠) while 𝑄 ≠ 𝑛𝑢𝑙𝑙 𝑣 = DEQUEUE(𝑄) for each 𝑢 ∈ 𝐴𝑑𝑗[𝑣] if 𝑢. 𝑠𝑡𝑎𝑡𝑒 == 𝑢𝑛𝑣𝑖𝑠𝑖𝑡𝑒𝑑 𝑢. 𝑠𝑡𝑎𝑡𝑒 = 𝑣𝑖𝑠𝑖𝑡𝑒𝑑 𝑢. 𝑑𝑖𝑠𝑡 = 𝑣. 𝑑𝑖𝑠𝑡 + 1 𝑢. 𝑝𝑟𝑒𝑑 = 𝑣 ENQUEUE(𝑄, 𝑢) 𝑣. 𝑠𝑡𝑎𝑡𝑒 = 𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑒 Depth-First Search DFS(𝑉, 𝐸): for each vertex 𝑣 ∈ 𝑉 𝑣. 𝑠𝑡𝑎𝑡𝑒 = 𝑢𝑛𝑣𝑖𝑠𝑖𝑡𝑒𝑑 𝑣. 𝑝𝑟𝑒𝑑 = 𝑛𝑢𝑙𝑙 for each vertex 𝑣 ∈ 𝑉 if 𝑣. 𝑠𝑡𝑎𝑡𝑒 == 𝑢𝑛𝑣𝑖𝑠𝑖𝑡𝑒𝑑 DFS-VISIT(𝑉, 𝐸, 𝑣) DFS-VISIT(𝑉, 𝐸, 𝑣): 𝑣. 𝑠𝑡𝑎𝑡𝑒 = 𝑣𝑖𝑠𝑖𝑡𝑒𝑑 for each 𝑢 ∈ 𝐴𝑑𝑗[𝑣] if 𝑢. 𝑠𝑡𝑎𝑡𝑒 == 𝑢𝑛𝑣𝑖𝑠𝑖𝑡𝑒𝑑 𝑢. 𝑝𝑟𝑒𝑑 = 𝑣 DFS-VISIT(𝑉, 𝐸, 𝑢): 𝑣. 𝑠𝑡𝑎𝑡𝑒 = 𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑒 // Explore edge (𝑣, 𝑢) // Done with 𝑣 Depth-First Search: Example 𝑟 𝑠 𝑡 𝑢 𝑣 𝑤 𝑥 𝑦 Status Unvisited Visited Complete Depth-First Search: Example 𝑟 𝑠 𝑡 𝑢 𝑣 𝑤 𝑥 𝑦 Status Unvisited Visited Complete Depth-First Search: Example 𝑟 𝑠 𝑡 𝑢 𝑣 𝑤 𝑥 𝑦 Status Unvisited Visited Complete Depth-First Search: Example 𝑟 𝑠 𝑡 𝑢 𝑣 𝑤 𝑥 𝑦 Status Unvisited Visited Complete Depth-First Search: Example 𝑟 𝑠 𝑡 𝑢 𝑣 𝑤 𝑥 𝑦 Status Unvisited Visited Complete Depth-First Search: Example 𝑟 𝑠 𝑡 𝑢 𝑣 𝑤 𝑥 𝑦 Status Unvisited Visited Complete Depth-First Search: Example 𝑟 𝑠 𝑡 𝑢 𝑣 𝑤 𝑥 𝑦 Status Unvisited Visited Complete Depth-First Search: Example 𝑟 𝑠 𝑡 𝑢 𝑣 𝑤 𝑥 𝑦 Status Unvisited Visited Complete Depth-First Search: Example 𝑟 𝑠 𝑡 𝑢 𝑣 𝑤 𝑥 𝑦 Status Unvisited Visited Complete Depth-First Search: Example 𝑟 𝑠 𝑡 𝑢 𝑣 𝑤 𝑥 𝑦 Status Unvisited Visited Complete Depth-First Search: Example 𝑟 𝑠 𝑡 𝑢 𝑣 𝑤 𝑥 𝑦 Status Unvisited Visited Complete Depth-First Search: Example 𝑟 𝑠 𝑡 𝑢 𝑣 𝑤 𝑥 𝑦 Status Unvisited Visited Complete Depth-First Search: Example 𝑟 𝑠 𝑡 𝑢 𝑣 𝑤 𝑥 𝑦 Status Unvisited Visited Complete Depth-First Search: Example 𝑟 𝑠 𝑡 𝑢 𝑣 𝑤 𝑥 𝑦 Status Unvisited Visited Complete Depth-First Search: Example 𝑟 𝑠 𝑡 𝑢 𝑣 𝑤 𝑥 𝑦 Status Unvisited Visited Complete Depth-First Search: Example 𝑟 𝑠 𝑡 𝑢 𝑣 𝑤 𝑥 𝑦 Status Unvisited Visited Complete 𝑻 𝒏 = 𝑶(𝑽 + 𝑬) Analysis of Depth-First Search Θ(|𝑉|) |𝑉| times 𝑂 𝐴𝑑𝑗 𝑣 DFS(𝑉, 𝐸): for each vertex 𝑣 ∈ 𝑉 𝑣. 𝑠𝑡𝑎𝑡𝑒 = 𝑢𝑛𝑣𝑖𝑠𝑖𝑡𝑒𝑑 𝑣. 𝑝𝑟𝑒𝑑 = 𝑛𝑢𝑙𝑙 for each vertex 𝑣 ∈ 𝑉 if 𝑣. 𝑠𝑡𝑎𝑡𝑒 == 𝑢𝑛𝑣𝑖𝑠𝑖𝑡𝑒𝑑 DFS-VISIT(𝑉, 𝐸, 𝑣) DFS-VISIT(𝑉, 𝐸, 𝑣): 𝑣. 𝑠𝑡𝑎𝑡𝑒 = 𝑣𝑖𝑠𝑖𝑡𝑒𝑑 for each 𝑢 ∈ 𝐴𝑑𝑗[𝑣] if 𝑢. 𝑠𝑡𝑎𝑡𝑒 == 𝑢𝑛𝑣𝑖𝑠𝑖𝑡𝑒𝑑 𝑢. 𝑝𝑟𝑒𝑑 = 𝑣 DFS-VISIT(𝑉, 𝐸, 𝑢): 𝑣. 𝑠𝑡𝑎𝑡𝑒 = 𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑒 // Explore edge (𝑣, 𝑢) // Done with 𝑣 DFS/BFS Applications BFS Applications ◦ ◦ ◦ ◦ ◦ Minimum spanning tree for unweighted graphs Shortest paths for unweighted graphs Cycle detection undirected graphs Bipartite testing Network Packet Broadcasting DFS Applications ◦ ◦ ◦ ◦ Minimum spanning tree for unweighted graphs Cycle detection in directed (or undirected) graphs Connected components Topological sorting Connected Components Definition: A strongly connected component of 𝐺 is a subgraph 𝐻 of 𝐺 where every vertex 𝑣 in 𝐻 is reachable from every other vertex 𝑢 in 𝐻. This graph has 5 strongly connected components Connected Components Using DFS to find the strongly connected components: ◦ Kosaraju Algorithm ◦ Tarjan Algorithm