Chapter 4 - Graph.pptx

Introduction to Algorithms - 401115  Chapter 4 Graph 2  3 Agenda Introduction (the 7 bridges of Königsberg problem) What is Graph? Graph presentation. Breadth First Search. Depth First Search. Dijkstra’s Algorithm. Kruskal’s Al...

Introduction to Algorithms - 401115  Chapter 4 Graph 2  3 Agenda Introduction (the 7 bridges of Königsberg problem) What is Graph? Graph presentation. Breadth First Search. Depth First Search. Dijkstra’s Algorithm. Kruskal’s Algorithm. Prim's algorithm The Seven Bridges of Königsberg Problem Part 1 4 The 7 Bridges of 5 Königsberg Leonhard Euler, (pronounced “oiler”) was a Swiss mathematician whose power of mental calculation was prodigious. As a teenager his fame quickly spread throughout Europe and at the age of 20 he was summoned by Catherine 1st of Russia to study at the Academy of Science at St Petersburg. He became Professor of Physics at 23 and Professor of mathematics at 26. At the Academy he contributed to numerous branches of mathematics and other sciences, including work on optics and the study of planetary motion. He made progress towards solving “Fermat’s Last Theorem” and introduced the notation for Pi () and sigma (). At 31 he lost the sight in his right eye and later became almost totally blind. He had thirteen children of whom only five survived their The 7 Bridges of 6 Königsberg Whilst working at the academy Euler got to hear of the problem of the 7 Bridges of Königsberg. The river Pregel ran through the town and divided it into 4 land areas, one of which was an island in the middle. The river was spanned by seven bridges and the people of the town tried to walk a route around the center that crossed all seven bridges once and only once. Use your worksheet to try and find a route around the center, crossing all seven bridges, once and only once. You can start your journey from any point in the town and you can finish at any point. The 7 Bridges of 7 Königsberg Use your worksheet to try and find a route around the center, crossing all seven bridges, once and only once. You can start your journey from any point in the town and you can finish at any point. This is equivalent to drawing the network on paper without lifting your pencil or going over a line once drawn. The 7 Bridges of 8 Königsberg During his investigation, Euler defined an even vertex and an odd vertex. An odd vertex has an odd number of arcs connected to it and an even vertex has an even number of arcs connected to it. 𝑠𝑡𝑎𝑟𝑡=𝑒𝑛𝑑 If a graph has an Eulerian walk then the number of odd degree vertices is either 0 or 2 𝑠𝑡𝑎𝑟𝑡 ≠𝑒𝑛𝑑  9 Euler circuits and paths An Euler circuit in a graph is a simple circuit containing every edge of the graph. An Euler path in a graph is a simple path containing every edge of the graph. Theorem 1: A finite graph has an Euler circuit if and only if it is connected and all vertices have even degree. Theorem 2: A finite graph has an Euler path (but not an Euler circuit) if and only if it is connected and exactly two vertices have odd degrees. Graph Terminology Part 2 10  11 What is a Graph? A Graph G is an order pair where is a (finite) set of elements (vertices) and is a set of 2-subsets of V (set of edges) Simple Graph No loops, no multiple edges Directed Graph Each edge has a direction associated to it The edges are presented in order pairs: 𝐸={(1,2), (3,2),(1,3)} Example: Not a simple graph multiple edges loop s  12 Terminology End vertices (or endpoints) of an edge  U and V are the endpoints of edge Edges incident on a vertex  , , and are incident on V Degree of a vertex  X has degree 5 (number of edges coming out of it) Parallel edges  and are parallel edges Self-loop  is a self-loop Adjacent vertices  U and V are adjacent (neighbor) Adjacent edges  and are adjacent (as they share the same end point)  13 Terminology (cont.) Path  Sequence of alternating vertices and edges  Begins with vertex  Ends with vertex  Each edge is preceded and followed by its endpoints Simple path  Path such that all its vertices and edges are distinct Examples  is a simple path  is a path that is not simple  14 Properties Property 1  Proof: each edge is counted twice Property 2  In an undirected graph with no self-loops and no multiple edges  Proof: each vertex has degree at most Notation  number of vertices, also called order of graph  number of edges, also called size of graph  degree of vertex Example The ways to represent 15 a Graph Adjacency matrix Incidence matrix  Rows represent vertices  Rows represent vertices  Columns represent vertices  Columns represent edges 0 1 2 3 0 1 1 0 The “old fashioned” 1 0 1 0 version just 1 1 0 0 1 1 0 1 has 0 for no edge and 1 1 0 1 0 0 0 1 0 for edge 0 1 1 1 0 1 2 3 0 0 0 1  Graph Traversal Breadth-First Search Part 3-A 16  17 Breadth-First Search star Breadth First Search (BFS) algorithm t traverses a graph in a breadth-ward motion (Level by Level) and uses a queue to remember to get the next vertex to start a search, when a dead end occurs in any iteration. As in the example given above, BFS algorithm traverses from S to A, from S to B, From S to C, it then goes to D through A, to E through B, to F through C, and finally goes to G through D. It employs the following rules:  Rule 1: Visit the adjacent unvisited vertex. Mark it as visited. Display it. Dead Insert it in a queue. End  Rule 2: If no adjacent vertex is found, remove the first vertex from the BFS on a graph with vertices and edges takes time queue. Example: 18 Traverse the graph using BFS Unexplored vertex Visited vertex Unexplored edge Discovery edge Cross edge Example: 19 Traverse the graph using BFS 𝐿0 𝐿1 Unexplored vertex Visited vertex Unexplored edge Discovery edge Cross edge Example: 20 Traverse the graph using BFS 𝐿0 𝐿1 Unexplored vertex Visited vertex Unexplored edge Discovery edge Cross edge Example: 21 Traverse the graph using BFS 𝐿0 𝐿1 Unexplored vertex Visited vertex Unexplored edge Discovery edge Cross edge Example: 22 Traverse the graph using BFS 𝐿0 𝐿1 Unexplored vertex Visited vertex Unexplored edge Discovery edge Cross edge Example: 23 Traverse the graph using BFS 𝐿0 𝐿1 𝐿2 Unexplored vertex Visited vertex Unexplored edge Discovery edge Cross edge Example: 24 Traverse the graph using BFS 𝐿0 𝐿1 𝐿2 Unexplored vertex Visited vertex Unexplored edge Discovery edge Cross edge Example: 25 Traverse the graph using BFS 𝐿0 𝐿1 𝐿2 Unexplored vertex Visited vertex Unexplored edge Discovery edge Cross edge Example: 26 Traverse the graph using BFS 𝐿0 𝐿1 𝐿2 Unexplored vertex Visited vertex Unexplored edge Discovery edge Cross edge Example: 27 Traverse the graph using BFS 𝐿0 𝐿1 𝐿2 Unexplored vertex Visited vertex Unexplored edge Discovery edge Cross edge Example: 28 Traverse the graph using BFS 𝐿0 𝐿1 𝐿2 Unexplored vertex Visited vertex Unexplored edge Discovery edge Cross edge Example: 29 Traverse the graph using BFS 𝐿0 𝐿1 𝐿2 Unexplored vertex Visited vertex Unexplored edge Discovery edge Cross edge  30 BFS - C++ code  31 BFS - Python code  32 Properties Notation  Connected component of Property 1:  visits all the vertices and edges of Property 2:  The discovery edges labeled by form a spanning tree of 𝐿0 Property 3: 𝐿1  For each vertex in The path of from to has edges Every path from to in has at least 𝐿2 edges  Graph Traversal Depth-First Search Part 3-B 33  34 Depth-First Search Depth First Search (DFS) algorithm traverses a graph in a depth-ward motion and uses a stack to remember to get the next vertex to start a search, when a dead end occurs in any iteration. As in the example given above, DFS algorithm traverses from S to A to D to G to E to B first, then to F and lastly to G. It employs the following rules:  Rule 1: Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a stack.  Rule 2: If no adjacent vertex is found, pop up a vertex from the stack. (It will pop up all the vertices from the stack, which do not have adjacent vertices.) DFS on a graph with vertices and Ruleedges takes 3: Repeat time Rule 1 and Rule 2 Example: 35 Traverse the graph using DFS Unexplored vertex Visited vertex Unexplored edge Discovery edge Cross edge Example: 36 Traverse the graph using DFS Unexplored vertex Visited vertex Unexplored edge Discovery edge Cross edge Example: 37 Traverse the graph using DFS Unexplored vertex Visited vertex Unexplored edge Discovery edge Cross edge Example: 38 Traverse the graph using DFS Unexplored vertex Visited vertex Unexplored edge Discovery edge Cross edge Example: 39 Traverse the graph using DFS Unexplored vertex Visited vertex Unexplored edge Discovery edge Cross edge Example: 40 Traverse the graph using DFS Unexplored vertex Visited vertex Unexplored edge Discovery edge Cross edge Example: 41 Traverse the graph using DFS Unexplored vertex Visited vertex Unexplored edge Discovery edge Cross edge Example: 42 Traverse the graph using DFS Unexplored vertex Visited vertex Unexplored edge Discovery edge Cross edge Example: 43 Traverse the graph using DFS Unexplored vertex Visited vertex Unexplored edge Discovery edge Cross edge  44 DFS - C++ code  45 DFS - Python code Breadth-First Search vs. Depth-First Search Part 3-C 46  47 DFS vs. BFS DFS BFS 𝐿0 𝐿1 𝐿2  48 DFS vs. BFS  DFS Spanning Tree:  BFS Spanning Tree: Dijkstra's algorithm Part 4 49  50 Dijkstra's algorithm Dijkstra's algorithm: finds shortest (minimum weight) path between a particular pair of vertices in a weighted directed graph with nonnegative edge weights.  solves the "one vertex, shortest path" problem  basic algorithm concept: create a table of information about the currently known best way to reach each vertex (distance, previous vertex) and improve it until it reaches the best solution. In a graph where:  vertices represent cities,  edge weights represent driving distances between pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between one city and any other. Dijkstra algorithm works for directed as well as undirected graphs.  51 Dijkstra's algorithm Problem Statement:  For a connected edge weight graph and a source vertex. Find the minimum weight of a path from to every other vertex in. Let be the weight function. Solution Steps: 1. Set which will store the vertices of for which a shortest path has been found. 2. Set labeling function and for all , and add to. 3. Let w be the newest member of , for each , , set  [hint: means the set of all vertices neighbor to the node ] 4. Pick any with minimum and add to & Repeat step 3 Solution:  For each is the minimum weight of a path in with weight function. Example: Dijkstra's 52 algorithm  53 Example: Initialization Distance (source) =  Pick vertex in List with minimum distance  54 Example: Update neighbors' distance 𝑺 ={ 𝑨 }  55 Example: Remove vertex with minimum distance 𝑺 ={ 𝑨 , 𝑫 }  56 Example: Update neighbors 𝑺 ={ 𝑨 , 𝑫 }  57 Example: Pick vertex in List with minimum distance(B) and update neighbors  Note: not updated since D is already known (visited) and not updated since it is larger than previous computed 𝑺 ={ 𝑨 , 𝑫 , 𝑩 }  58 Example: Pick vertex in List with minimum distance(E) and update neighbors  Note: not updated since it is larger than previous computed 𝑺 ={ 𝑨 , 𝑫 , 𝑩 , 𝑬 }  59 Example: Pick vertex in List with minimum distance(C) and update neighbors  𝑺 ={ 𝑨 , 𝑫 , 𝑩 , 𝑬 , 𝑪 }  60 Example: Pick vertex in List with minimum distance(G) 6  Previous distance 𝑺 ={ 𝑨 , 𝑫 , 𝑩 , 𝑬 , 𝑪 , 𝑮 }  61 Example: Pick vertex not in S with lowest cost (F) and update neighbors  If you were asked to find the shortest path from A to G, you can use this algorithm until you reach G and stop.  The cost will be the distance from A to G  The path will be 6 𝑺 ={ 𝑨 , 𝑫 , 𝑩 , 𝑬 , 𝑪 , 𝑮 , 𝑭 }  62 Correctness Dijkstra’s algorithm is a greedy algorithm  make choices that currently seem the best (the shortest)  locally optimal does not always mean globally optimal Correct because maintains following two properties:  for every known (visited) vertex, recorded distance is shortest distance to that vertex from source vertex.  for every unknown vertex , its recorded distance is shortest path distance to from source vertex, considering only currently Minimum Spanning Tree Part 5 63 Minimum Spanning 64 Tree Tree: a connected, directed acyclic graph Spanning Tree: a subgraph of a graph, which meets the constraints to be a tree (connected, acyclic) and connects every vertex of the original graph. Minimum Spanning Tree: a spanning tree with weight less than or equal to any other spanning tree for the given graph. Minimum Spanning 65 Tree for the previous example: The shortest path (route) cost is Kruskal’s Algorithm Part 6 66  67 Kruskal’s Algorithm Work with edges, rather than nodes Two steps:  Sort edges by increasing edge weight  Select the first edges that do not generate a cycle Kruskal's algorithm to find the minimum cost spanning tree uses the greedy approach. This algorithm treats the graph as a forest and every node it has as an individual tree. A tree connects to another if and only if, it has the least cost among all available options and does not violate MST properties. The given graph must be weighted, connected and undirected. MST: minimum spanning tree  Kruskal’s Algorithm 68 step by step Consider an undirected, weight Step 1 - Remove all loops and graph Parallel Edges: Remove all loops and parallel edges from the given graph. In case of parallel edges, keep the one which has the least cost associated and remove all others. Step 2 - Arrange all edges in their increasing order of weight: create a set of edges and weight, and arrange them in an ascending order of weightage (cost). Step 3 - Add the edge which has the least weightage: start adding edges to the graph beginning from the one which has the least weight. Throughout, we shall keep checking that the spanning properties remain intact. In case, by adding one edge, the spanning tree property does not hold then we shall consider not to include the edge in the graph(If Kruskal’s Algorithm 69 step by step Step 2 - Arrange all edges in their increasing order of weight: Sort the edges by increasing edge weight  Kruskal’s Algorithm 70 step by step Select first edges which does not generate a cycle ✓ 𝑺 ={ 𝑫 , 𝑬 }  Kruskal’s Algorithm 71 step by step Step 3 – Add the edge which has the least weightage ✓ ✓ 𝑺 ={ 𝑫 , 𝑬 , 𝑮 }  Kruskal’s Algorithm 72 step by step Select first edges which does not generate a cycle ✓ ✓ ✗ Accepting edge (E,G) would 𝑺 ={ 𝑫 , 𝑬 , 𝑮 } create a cycle  Kruskal’s Algorithm 73 step by step Step 3 - Add the edge which has the least weightage: start adding edges to the graph beginning from the one which has the least weight. ✓ ✓ ✗ ✓ 𝑺 ={ 𝑫 , 𝑬 , 𝑮 , 𝑪 }  Kruskal’s Algorithm 74 step by step ✓ ✓ ✗ ✓ ✓ 𝑺 ={ 𝑫 , 𝑬 , 𝑮 , 𝑪 , 𝑯 }  Kruskal’s Algorithm 75 step by step ✓ ✓ ✗ ✓ ✓ ✓ 𝑺 ={ 𝑫 , 𝑬 , 𝑮 , 𝑪 , 𝑯 , 𝑭 }  Kruskal’s Algorithm 76 step by step ✓ ✓ ✗ ✓ ✓ ✓ ✓ 𝑺 ={ 𝑫 , 𝑬 , 𝑮 , 𝑪 , 𝑯 , 𝑭 , 𝑩 }  Kruskal’s Algorithm 77 step by step ✓ ✗ ✓ ✗ ✓ ✓ ✓ ✓ 𝑺 ={ 𝑫 , 𝑬 , 𝑮 , 𝑪 , 𝑯 , 𝑭 , 𝑩 }  Kruskal’s Algorithm 78 step by step ✓ ✗ ✓ ✗ ✗ ✓ ✓ ✓ ✓ 𝑺 ={ 𝑫 , 𝑬 , 𝑮 , 𝑪 , 𝑯 , 𝑭 , 𝑩 }  Kruskal’s Algorithm 79 step by step ✓ ✗ ✓ ✗ ✗ ✗ ✓ ✓ ✓ ✓ 𝑺 ={ 𝑫 , 𝑬 , 𝑮 , 𝑪 , 𝑯 , 𝑭 , 𝑩 }  Kruskal’s Algorithm 80 step by step ✓ ✗ ✓ ✗ ✗ ✗ ✓ ✓ ✓ ✓ ✓ 𝑺={ 𝑫 , 𝑬 , 𝑮 , 𝑪 , 𝑯 , 𝑭 , 𝑩 , 𝑨 }  Kruskal’s Algorithm 81 step by step Select first edges which does not generate a cycle Minimum Spanning Tree: ✓ ✗ ✓ ✗ ✗ ✗ ✓ ✓ ✓ Considere Notes: ✓ Not 1. If there are same weights on some d edges may be we get different ✓ spanning tree but the minimum cost will stay the same. 2. It is possible also to find the Done ✓ 𝑺={ 𝑫 , 𝑬 ,spanning Maximum 𝑮,𝑪 , 𝑯 tree., 𝑭 , 𝑩 , 𝑨 } Time Complexity for Dijkstra's algorithm & Kruskal’s Algorithm Part 7 82  83 Time Complexity For a graph with is the number of edges, and is the number of vertices. Time complexity of the Dijkstra algorithm:  Time Complexity of the Dijkstra algorithm is if it is implemented using “the adjacency matrix representation”. However, this complexity is reduced to if the Binary Heap is implemented. Time complexity of the Kruskal algorithm:  Time Complexity is or. Sorting of edges takes time. After sorting, we iterate through all edges and apply find- union algorithm. The find and union operations can take at most time. So overall complexity is time. The value of can be at most , so are same. Therefore, overall time complexity is or. Prim’s Algorithm Part 8 84  85 Prim’s Algorithm Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph (to calculate the shortest path between two nodes in a graph). Prim's algorithm finds the subset of edges that includes every vertex of the graph such that the sum of the weights of the edges can be minimized. Prim's algorithm starts with the single node and explore all the adjacent nodes with all the connecting edges at every step. The edges with the minimal weights causing no cycles in the graph got selected.  86 Prim’s Algorithm The algorithm steps:  Step 1: Select a starting vertex  Step 2: Repeat Steps 3 and 4 until there are fringe vertices  Step 3: Select an edge e connecting the tree vertex and fringe vertex that has minimum weight  Step 4: Add the selected edge and the vertex to the minimum spanning tree T  [END OF LOOP]  Step 5: EXIT  87 Prim’s Algorithm Example: Construct a minimum spanning tree of the graph given in the following figure by using prim's algorithm. Solution: Step 1 : Choose a starting vertex. Step 2: Add the vertices that are adjacent to. Step 3: Choose the edge with the minimum weight among all. i.e. and add it to MST. Add the adjacent vertices of i.e. E and. Choose the edge with the minimum weight among all. In this case, the edges and then are such edges. Add them to MST and explore the adjacent of i.e. E and. Step 4: Choose the edge with the minimum weight i.e.. We can't choose as it would cause cycle in the graph. The graph produces in the step 4 is the minimum spanning tree of the graph shown in the above figure. The cost of MST will be calculated as:  88 Prim’s Algorithm Construct a MST of the graph given in the following figure by using prim's algorithm.  89 Prim’s Algorithm Step 1: 𝑺 ={ 𝑩 }  90 Prim’s Algorithm Step 2: 𝑺 ={ 𝑩 }  91 Prim’s Algorithm Step 3: 𝑺 ={ 𝑩 , 𝑫 }  92 Prim’s Algorithm Step 4: 𝑺 ={ 𝑩 , 𝑫 , 𝑬 }  93 Prim’s Algorithm Step 5: 𝑺 ={ 𝑩 , 𝑫 , 𝑬 , 𝑪 }  94 Prim’s Algorithm Step 5: 𝑺 ={ 𝑩 , 𝑫 , 𝑬 , 𝑪 ,𝑨 𝒄𝒐𝒔𝒕 ( 𝑴𝑺𝑻 } )=𝟒+𝟏+ 𝟐+𝟑=𝟏𝟎 𝒖𝒏𝒊𝒕𝒔 Prim’s Algorithm: 95 Example 𝑺 ={ } Prim’s Algorithm: 96 Example 𝑺 ={ 𝒂 }  Prim’s Algorithm: 97 Example 𝑺 ={ 𝒂 , 𝒃 }  Prim’s Algorithm: 98 Example 𝑺 ={ 𝒂 , 𝒃 , 𝒄 }  Prim’s Algorithm: 99 Example 𝑺 ={ 𝒂 , 𝒃 , 𝒄. 𝒊 }  Prim’s Algorithm: 100 Example 𝑺 ={ 𝒂 , 𝒃 , 𝒄. 𝒊 , 𝒇 }  Prim’s Algorithm: 101 Example 𝑺 ={𝒂 , 𝒃 , 𝒄. 𝒊 , 𝒇 , 𝒈 }  Prim’s Algorithm: 102 Example 𝑺 ={𝒂 , 𝒃 , 𝒄. 𝒊 , 𝒇 , 𝒈 , 𝒉 }  Prim’s Algorithm: 103 Example 𝑺 ={𝒂 , 𝒃 , 𝒄. 𝒊 , 𝒇 , 𝒈 , 𝒉 , 𝒅 }  Prim’s Algorithm: 104 Example 𝑺 ={𝒂 , 𝒃 , 𝒄. 𝒊 , 𝒇 , 𝒈 , 𝒉 , 𝒅 , 𝒆 }  Prim’s Algorithm: 105 Example Minimum Spanning Tree: 𝑺 ={𝒂 , 𝒃 , 𝒄. 𝒊 , 𝒇 , 𝒈 , 𝒉 , 𝒅( 𝑴𝑺𝑻 𝒄𝒐𝒔𝒕 , 𝒆 } )=𝟒+𝟖+ 𝟐+𝟒+ 𝟐+𝟏+𝟕+𝟗=𝟑𝟕 𝒖𝒏𝒊𝒕𝒔 Paradigms of Algorithms Part 9 106 Paradigms of 107 Algorithms Brute force: In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement. e.g. Selection and insertion sort algorithms. Greedy Algorithms: The solution is constructed through a sequence of steps. At each step the next optimal step is selected locally, without considering whether this step leads to the final global optimal solution or not. e.g. Kruskal, Dijkstra algorithm. Divide-and-Conquer: Divide the problem instance to several smaller sub-instances then solve each one independently. Finally, the solutions of these sub-instances are combined to form final solution. e.g. Merge and quick sort algorithm. Dynamic Programming: Solve problem of divide-conquer where identical sub-instances are computed repeatedly. End of Chapter 4 108