Algorithms Analysis and Design PDF

Algorithms Analysis and Design Chapter 3: Exhaustive Search: Graph Traversals (DFS and BFS) 1  Graph Terminology  A graph G = (V, E)  V = set of vertices (nodes or points)  E = set of edges (arcs or lines) = subset...

Algorithms Analysis and Design Chapter 3: Exhaustive Search: Graph Traversals (DFS and BFS) 1  Graph Terminology  A graph G = (V, E)  V = set of vertices (nodes or points)  E = set of edges (arcs or lines) = subset of V  V  Thus |E|  |V|2 = O(|V|2)  In an undirected graph:  edge(u, v) = edge(v, u)  In a directed graph:  edge(u,v) goes from vertex u to vertex v, notated uv  edge(u, v) is not the same as edge(v, u) 2  Graph Terminology A A B C B C D D Directed graph: Undirected graph: V = {A, B, C, D} V = {A, B, C, D} E = {(A,B), (A,C), (A,D), (C,B)} E = {(A,B), (A,C), (A,D), (C,B), (B,A), (C,A), (D,A), (B,C)} 3  Graph Terminology  Adjacent vertices: connected by an edge  Vertex v is adjacent to u if and only if (u, v)  E.  In an undirected graph with edge (u, v), and hence (v, u), v is adjacent to u and u is adjacent to v. a b a b c c d e d e Vertex a is adjacent to c and Vertex c is adjacent to a, but vertex c is adjacent to a vertex a is NOT adjacent to c 4  Graph Terminology  A Path in a graph from u to v is a sequence of edges between vertices w0, w1, …, wk, such that (wi, wi+1)  E, u = w0 and v = wk, for 0  i  k  The length of the path is k, the number of edges on the path a b a b c c d e d e abedce is a path. acde is a path. cdeb is a path. abec is NOT a path. bca is NOT a path. 5  Graph Terminology  Loops  If the graph contains an edge (v, v) from a vertex to itself, then the path v, v is sometimes referred to as a loop. a b c d e  The graphs we will consider will generally be loopless.  A simple path is a path such that all vertices are distinct, except that the first and last could be the same. a b c abedc is a simple path. cdec is a simple path. d e abedce is NOT a simple path. 6  Graph Terminology  simple path: no repeated vertices 7  Graph Terminology  Cycles  A cycle in a directed graph is a path of length at least 2 such that the first vertex on the path is the same as the last one; if the path is simple, then the cycle is a simple cycle. a b abeda is a simple cycle. c abeceda is a cycle, but is NOT a simple cycle. abedc is NOT a cycle. d e  A cycle in a undirected graph  A path of length at least 3 such that the first vertex on the path is the same as the last one.  The edges on the path are distinct. a b aba is NOT a cycle. abedceda is NOT a cycle. c abedcea is a cycle, but NOT simple. abea is a simple cycle. d e 8  Graph Terminology  If each edge in the graph carries a value, then the graph is called weighted graph.  A weighted graph is a graph G = (V, E, W), where each edge, e  E is assigned a real valued weight, W(e).  A complete graph is a graph with an edge between every pair of vertices.  A graph is called complete graph if every vertex is adjacent to every other vertex. 9  Graph Terminology  Complete Undirected Graph  has all possible edges n=1 n=2 n=3 n=4 10  Graph Terminology  subgraph: subset of vertices and edges forming a graph  A graph Gs = (Vs, Es) is a subgraph of a graph G = (V, E) if Vs  V, Es  E, and Es  VsVs. e 6 6 4 a 4 d a 4 d a d 1 5 3 1 1 b c b b 2 G is a sub-graph Not a sub-graph since, Es = {1,4,6}  Vs  Vs = {1,4} 11  Graph Terminology  connected graph: any two vertices are connected by some path  An undirected graph is connected if, for every pair of vertices u and v there is a path from u to v.  connected component: maximal connected subgraph. E.g., the graph below has 3 connected components 12  Graph Terminology  A directed graph is strongly connected if, for every pair of vertices u and v there is a path from u to v.  Note that in a directed graph, the existence of a path from u to v does not imply there is a path from v to u.  A directed graph that is not strongly connected, but the underlying graph is connected, is called weakly connected.  A symmetric digraph is a directed graph, G = (V, E), such that if (u, v)  E, then (v, u)  E. 13  Graph Terminology  tree - connected graph without cycles  forest - collection of trees 14 Graph Terminology 15  Graph Terminology  End vertices (or endpoints) of an edge  U and V are the endpoints of a  Edges incident on a vertex  a, d, and b are incident on V V  Adjacent vertices a b h j  U and V are adjacent  Degree of a vertex U d X Z  X has degree 5 c e i  Parallel edges W g  h and i are parallel edges  Self-loop f Y  j is a self-loop 16  Again... Remember...!  Path  sequence of alternating vertices and edges  begins with a vertex  ends with a vertex V  each edge is preceded and a b followed by its endpoints P1  Simple path U d X Z  path such that all its vertices and P2 h edges are distinct. c e  Examples  P1 = (V, X, Z) is a simple path. W g P2 = (U, W, X, Y, W, V) is a path  that is not simple. f Y 17  Again... Remember...!  Cycle  circular sequence of alternating vertices and edges  each edge is preceded and followed by its endpoints V  Simple cycle a b  cycle such that all its vertices and edges are distinct U d X Z  Examples C2 h  C1 = (V, X, Y, W, U, V) is a e C1 c simple cycle W g  C2 = (U, W, X, Y, W, V, U) is a cycle that is not simple f Y 18  Number of Edges  Each edge is of the form (u, v), u  v  Number of such pairs in an n vertex graph is n(n-1)  Undirected Graph  Since edge(u, v) is the same as edge(v, u), the number of edges in a complete undirected graph is n(n-1)/2  Number of edges in an undirected graph is  n(n-1)/2  Directed Graph  Since edge(u, v) is not the same as edge(v, u), the number of edges in a complete directed graph is n(n-1)  Number of edges in a directed graph is  n(n-1) 19  Vertex Degree  degree (of a vertex): # of adjacent vertices  degree(2) = 2, degree(5) = 3, degree(3) = 1 2 3 8 1 10 4 5 9 11 6 7 20  Sum of Vertex Degrees  Sum of degrees of all vertex = 2|E|  Since adjacent vertices each count the adjoining edge, it will be counted twice 8 10 9 11  deg(v)  2(# of edges) vV 21  In-Degree of a Vertex  in-degree is number of incoming edges  indegree(2) = 1, indegree(8) = 0 2 3 8 1 10 4 5 9 11 6 7 22  Out-Degree of a Vertex  out-degree is number of outbound edges  outdegree(2) = 1, outdegree(8) = 2 2 3 8 1 10 4 5 9 11 6 7 23  Sum of In-Degree and Out-Degree  Each edge contributes 1 to the in-degree of some vertex and 1 to the out-degree of some other vertex  Sum of in-degrees = sum of out-degrees = |E|,  where |E| is the number of edges in the digraph 24 Applications: Communication Network  vertex = city, edge = communication link 2 3 8 1 10 4 5 9 11 6 7 25  Driving Distance/Time Map  vertex = city,  edge weight = driving distance/time 2 4 3 8 8 1 6 10 2 4 5 4 4 3 5 9 11 5 6 6 7 7 26  Street Map  Some streets are one way  A bidirectional link represented by 2 directed edge  (5, 9) (9, 5) 2 3 8 1 10 4 5 9 11 6 7 27  Computer Networks  Electronic circuits cslab1a cslab1b  Printed circuit board math.brown.edu  Integrated circuit cs.brown.edu  Computer networks  Local area network brown.edu  Internet qwest.net  Web att.net cox.net John Paul David 28  Graphs  We will typically express running times in terms of  |V| = number of vertices, and  |E| = number of edges  If |E|  |V|2 the graph is dense‫كثيف‬  If |E|  |V| the graph is sparse‫متفرق‬  If you know you are dealing with dense or sparse graphs, different data structures may make sense 29  Graph Representation  Adjacency Matrix  Adjacency Lists 30  Adjacency Matrix  Assume V = {1, 2, …, n}  An adjacency matrix represents the graph as a n  n matrix A:  A[i, j] = 1 if edge(i, j)  E (or weight of edge) = 0 if edge(i, j)  E 31  Adjacency Matrix  Example: A 1 2 3 4 1 1 a d 2 2 4 3 b c ?? 3 4 32  Adjacency Matrix  Example: A 1 2 3 4 1 1 0 1 1 0 a d 2 0 0 1 0 2 4 b c 3 0 0 0 0 3 4 0 0 1 0 33  Adjacency Matrix  0/1 n  n matrix, where n = # of vertices  A(i, j) = 1 iff (i, j) is an edge 1 2 3 4 5 2 3 1 0 1 0 1 0 2 1 0 0 0 1 1 3 0 0 0 0 1 4 4 1 0 0 0 1 5 5 0 1 1 1 0 34  Adjacency Matrix 1 2 3 4 5 2 3 1 0 1 0 1 0 2 1 0 0 0 1 1 3 0 0 0 0 1 4 4 1 0 0 0 1 5 5 0 1 1 1 0 Diagonal entries are zero Adjacency matrix of an undirected graph is symmetric A(i, j) = A(j, i) for all i and j 35  Adjacency Matrix 1 2 3 4 5 2 3 1 0 0 0 1 0 2 1 0 0 0 1 1 3 0 0 0 0 0 4 4 0 0 0 0 1 5 5 0 1 1 0 0 Diagonal entries are zero Adjacency matrix of a digraph need not be symmetric 36  Adjacency Matrix  How much storage does the adjacency matrix require?  Answer: O(|V|2)  O(|V|) time to find vertex degree and/or vertices adjacent to a given vertex  What is the minimum amount of storage needed by an adjacency matrix representation of an undirected graph with 4 vertices?  Answer: 6 bits  Undirected graph matrix is symmetric  No self-loops don’t need diagonal 37  Adjacency Matrix  The adjacency matrix is a dense representation  Usually too much storage for large graphs  But can be very efficient for small graphs  If graph is unweighted, there is an additional advantage in storage for the adjacency matrix presentation; rather than using one word of computer memory for each matrix entry, the adjacency matrix uses only one bit per entry.  Most large interesting graphs are sparse  For this reason the adjacency list is often a more appropriate representation 38  Adjacency List  Adjacency list: for each vertex v  V, store a list of vertices adjacent to v.  Adjacency list for vertex i is a linear list of vertices adjacent from vertex i  Each adjacency list is a chain. 2 2 3 aList 4 1 5 1 5 5 1 4 5 2 4 3 # of chain nodes = 2|E| (undirected graph) # of chain nodes = |E| (digraph) 39 Adjacency List 40  Adjacency List  How much storage is required?  The degree of a vertex v = # incident edges Directed graphs have in-degree and out-degree  For directed graphs:  # of items in adjacency lists is  out-degree(v) = |E| takes (V + E) storage (Why?)  For undirected graphs: # items in adjacency lists is  degree(v) = 2|E| also (V + E) storage  So: Adjacency lists take O(V + E) storage 41  Graph Search Methods  Many graph problems solved using a search method  Path from one vertex to another  Is the graph connected?  etc.  Commonly used search methods:  Breadth-first search  Depth-first search 42  Graph Search Methods  A vertex u is reachable from vertex v iff there is a path from v to u.  A search method starts at a given vertex v and visits every vertex that is reachable from v. 2 3 8 1 4 5 9 10 6 7 11 43  Graph Search Methods  Given: a graph G = (V, E), directed or undirected  Goal: methodically explore every vertex and every edge  Ultimately: build a tree on the graph  Pick a vertex as the root  Choose certain edges to produce a tree  Note: might also build a forest if graph is not connected 44 Graph Traversal Algorithms Many problems require processing all graph vertices (and edges) in systematic fashion Graph traversal algorithms: Depth-first search (DFS) Breadth-first search (BFS) A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 3 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 45 Depth-First Search (DFS)  Visits graph’s vertices by always moving away from last visited vertex to unvisited one, backtracks if no adjacent unvisited vertex is available.  Uses a stack a vertex is pushed onto the stack when it’s reached for the first time a vertex is popped off the stack when it becomes a dead end, i.e., when there is no adjacent unvisited vertex  “Redraws” graph in tree-like fashion (with tree edges and back edges for undirected graph). A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 3 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 46 DFS Example 1 a, c, d, f, b, e, g, h, i, j A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 3 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 47 Pseudocode of DFS A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 3 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 48 DFS  To appreciate its true power and depth, you should trace the algorithm’s action by looking not at a graph’s diagram but at its adjacency matrix or adjacency lists.  This algorithm is quite efficient since it takes just the time proportional to the size of the data structure used for representing the graph in question. Thus, for the adjacency matrix representation, the traversal time is in (|𝑉|2), and for the adjacency list representation, it is in (|V|+|E|) where |V| and |E| are the number of the graph’s vertices and edges, respectively. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 3 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 49 DFS Example 2 A B C D E F Breadth-first search (BFS)  Visits graph vertices by moving across to all the neighbors of last visited vertex  Instead of a stack, BFS uses a queue  Similar to level-by-level tree traversal  “Redraws” graph in tree-like fashion (with tree edges and cross edges for undirected graph) A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 3 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 51 BFS Example 1 a, c, d, e, f, b, g, h, j, i A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 3 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 52 Pseudocode of BFS A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 3 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 53 BFS  Breadth-first search has the same efficiency as depth-first search: it is in (|𝑉|2) for the adjacency matrix representation and in (|V|+|E|) for the adjacency list representation.  Unlike depth-first search, it yields a single ordering of vertices because the queue is a FIFO (first-in first-out) structure and hence the order in which vertices are added to the queue is the same order in which they are removed from it. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 3 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 54 Overview F Breadth-first search starts C with given node A B D H 0 G E Task: Conduct a breadth-first search of the graph starting with node D Overview F Breadth-first search starts C with given node A Then visits nodes adjacent in B D some specified order (e.g., H alphabetical) 0 G E Like ripples in a pond 1 Nodes visited: D Overview F Breadth-first search starts C with given node A Then visits nodes adjacent in B D some specified order (e.g., H alphabetical) 0 G E Like ripples in a pond 1 Nodes visited: D, C Overview F Breadth-first search starts C with given node A Then visits nodes adjacent in B D some specified order (e.g., H alphabetical) 0 G E Like ripples in a pond 1 Nodes visited: D, C, E Overview F Breadth-first search starts C with given node A Then visits nodes adjacent in B D some specified order (e.g., H alphabetical) 0 G E Like ripples in a pond 1 Nodes visited: D, C, E, F Overview F When all nodes in ripple are C visited, visit nodes in next A ripples B D H 0 G E 2 1 Nodes visited: D, C, E, F, G  Overview F When all nodes in ripple are C visited, visit nodes in next A ripples B D H 0 3 G E 2 1 Nodes visited: D, C, E, F, G, H  Overview 4 F When all nodes in ripple are C visited, visit nodes in next A ripples B D H 0 3 G E 2 1 Nodes visited: D, C, E, F, G, H, A  Overview 4 F When all nodes in ripple are C visited, visit nodes in next A ripples B D H 0 3 G E 2 1 Nodes visited: D, C, E, F, G, H, A, B Walk-Through Enqueued Array F C A A B Q B C D H D E G E F G H How is this accomplished? Simply replace the stack with a queue! Rules: (1) Maintain an enqueued array. (2) Visit node when dequeued.  Walk-Through Enqueued Array F C A A B QD B C D H D √ E G E F G Nodes visited: H Enqueue D. Notice, D not yet visited.  Walk-Through Enqueued Array F C A A B QCEF B C √ D H D √ E √ G E F √ G Nodes visited: D H Dequeue D. Visit D. Enqueue unenqueued nodes adjacent to D.  Walk-Through Enqueued Array F C A A B QEF B C √ D H D √ E √ G E F √ G Nodes visited: D, C H Dequeue C. Visit C. Enqueue unenqueued nodes adjacent to C.  Walk-Through Enqueued Array F C A A B QFG B C √ D H D √ E √ G E F √ G Nodes visited: D, C, E H Dequeue E. Visit E. Enqueue unenqueued nodes adjacent to E.  Walk-Through Enqueued Array F C A A B QG B C √ D H D √ E √ G E F √ G √ Nodes visited: D, C, E, F H Dequeue F. Visit F. Enqueue unenqueued nodes adjacent to F.  Walk-Through Enqueued Array F C A A B QH B C √ D H D √ E √ G E F √ G √ Nodes visited: D, C, E, F, G H √ Dequeue G. Visit G. Enqueue unenqueued nodes adjacent to G.  Walk-Through Enqueued Array F C A √ A B √ QA B B C √ D H D √ E √ G E F √ G √ Nodes visited: D, C, E, F, G, H H √ Dequeue H. Visit H. Enqueue unenqueued nodes adjacent to H.  Walk-Through Enqueued Array F C A √ A B √ QB B C √ D H D √ E √ G E F √ G √ Nodes visited: D, C, E, F, G, H, A H √ Dequeue A. Visit A. Enqueue unenqueued nodes adjacent to A.  Walk-Through Enqueued Array F C A √ A B √ Q empty B C √ D H D √ E √ G E F √ G √ Nodes visited: D, C, E, F, G, H, H √ A, B Dequeue B. Visit B. Enqueue unenqueued nodes adjacent to B.  Walk-Through Enqueued Array F C A √ A B √ Q empty B C √ D H D √ E √ G E F √ G √ Nodes visited: D, C, E, F, G, H, H √ A, B Q empty. Algorithm done.