PowerPoint PresentationSlide 2Representation of GraphsEquivalence of Graph RepresentationsSlide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Proof of Theorem IProof of Theorem I (continued)Slide 19Slide 20101/14/19Graphs and Graph AlgorithmsGraphs are a pervasive data structure. Trees are a special form of graphs—connected and without a cycle.Graph Representationsadjacency matrixadjacency listlist of edgesGraph Algorithms:Searching a graph using BFS and DFSMST and shortest pathsTopological order201/14/19Representation of GraphsMathematical (set) representationG = (V, E), whereV = {v1, v2, ..., vn }E = {e1, e2, ..., em } and ek =(vi, vj)Adjacency Matrix142536123456/256564 /5 /Adjacency lists consist ofan array of n lists, one for each vertex in Vfor each u  V, u.adj stores a pointer to the linked list that contains the set {v | (u, v)  E}301/14/19Representation of GraphsWe can also use the list of edges as a representation of the graph. For example, for the previous graph, the list of edges would be:1 2 weight_of_this_edge1 4 weight_of_this_edge2 5 weight_of_this_edge3 5 weight_of_this_edge3 6 weight_of_this_edge4 5 weight_of_this_edge6 6 weight_of_this_edge401/14/19Equivalence of Graph RepresentationsEach of the graph representations describes the graph completely.With one representation, we can always get another representation.However, the efficiency varies among different representations.Please pay attention to this when we study graph algorithms.501/14/19Minimum Spanning Tree ProblemA weighted graph G = (V, E, w) adds a weight to each edge. w maps an edge e to a real number.A spanning tree T of a graph G is a subgraph of G, where V(T) = V(G) and E(T) spans V(G).A minimum-spanning-tree is the spanning tree with the lowest sum of weights.This is an optimization problem.bhcgdfia e481 2109782711 1446weighted graphbhcgdfia e41 297824A Minimum-Spanning Tree601/14/19Kruskal’s MST AlgorithmThis algorithm is based on disjoint-set operations. It is a greedy algorithm that always tries the local minimum.MST-Kruskal(G(V, E, W))1. T :=  (empty set)2. for each vertex v  V(G) do3. Make-Set(v)4. sort edges of E, in order by non-decreasing weight5. for each edge (u, v)  E(G) do6. if Find-Set(u)  Find-Set(v) then7. T := T  {(u, v)} // T is set of edges8. Union(u, v) //union by rank, takes: O( lg|E|)9. return T // set of verticesRunning time is O(|E|lg|E|)701/14/19Example of Kruskal’s MST Algorithmbhcgdfia e481 2109782711 1446bhcgdfia e481 2109782711 1446bhcgdfia e481 2109782711 1446bhcgdfia e481 2109782711 1446bhcgdfia e481 2109782711 1446bhcgdfia e481 2109782711 1446bhcgdfia e481 2109782711 1446bhcgdfia e481 2109782711 1446801/14/19Prim’s MST AlgorithmThis algorithm is similar to the breadth-first algorithm. It uses a priority queue Q based on a key field. For v  V(G)v.key = minimum(w(v, u)), u  V - Qv.key =  if there is no edge from v to any vertices in V-QOther fields of a vertex include:u.: Pointer to its parent (predecessor)u.adj: adjacent vertex set to uQr u vV-QxIt starts from any vertex r.901/14/19Prim’s MST AlgorithmMST-Prim(G(V, E, W), r)1. Q := V;2. for each vertex u  Q do3. u.key :=  4. u. := nil5. r.key := 0 //decrease-key operation6. while Q   do7. u := Extract-Min(Q)8. for each vertex v  u.adj do9. if v  Q and w(u, v) < v.key then10. v. := u11. v.key := w(u, v) //decrease-keyO(|V|)2|E|O(lg|V|)1001/14/19Prim’s MST Algorithm Running TimeThe total running time is then calculated as follows:Why does the while and for-loop iterate 2|E| times?Because the total length of all adj lists together = 2|E|, each edge (u, v) will be processed only once, andthere are two vertices in each edge. O(|V|) + O(lg|V|) + O(|V|)O(lg|V|) + 2|E|  O(lg|V|)= O(|E|  lg|V|)Which is same as Kruskal’s: O(|E|lg|E|). Why? |E| = O(|V|2)|E|lg|E|  |E|lg|V|2 = 2|E|lg|V|O(|E|lg|E|) = O(|E|lg|V|)1101/14/19bhcgdfia e481 2109782711 14464b c d e f g h i 4      8 Iteration 17- 11 Q8bhcgdfia e481 2109782711 14464c d e f g h i 8     8 Iteration 27- 11 Q88Example of Prim’s MST AlgorithmInitialize1 - 5 bhcgdfia e481 2109782711 1446a b c d e f g h i 0        Q01201/14/19bhcgdfia e481 2109782711 14464i d e f g h2 7  4  8Iteration 37- 11 Q88247bhcgdfia e41 2109782711 14464f d e g h 4 7  6 7 Iteration 47- 11 Q782476Example (contd.)bhcgdfia e41 2109782711 1444g d e h 2 7 10 7 Iteration 57- 11 Q78247210b cgdfia e41 210978211 1444h d e1 7 10Iteration 67- 11 Q18247610h1301/14/19bhcgdfia e41210978211 1444d e 7 10 Iteration 77- 11 Q782476Example (contd.)bhcgdfia e41 2978211 1444e 9 Iteration 77- 11 Q782476910bhcgdfia e41 297824bhcgdfia e41 2978211 1444 Iteration 77- 11 Q78247691401/14/19A Generic MST AlgorithmAdding one edge to the tree at a time.MST-Generic(G(V, E, W))1. T :=  (empty set)2. while T is not a spanning tree do3. find an edge (u, v) that is safe for T4. T := T  {(u, v)}5. return TAn edge e is safe for T, if adding e to T will not destroythe invariant that T remains to be a subset of an MST.1501/14/19Some ConceptsA cut of G(V, E) is a partition of vertices (V1, V2) so that the union of V1 and V2 is V, and the intersection of V1 and V2 is the empty set. An edge e is called a crossing edge of this cut if it connects a vertex in V1 with a vertex in V2. Let E1 be a subset of edges. Let (V1, V2) be a cut. We say that the cut respects E1 if no edge in E1 is a crossing edge.A light edge of a cut is a crossing edge with the smallest weight.1601/14/19Finding a Safe Edge, ITheorem ILet graph G = (V, E, w) be a connected undirected graph with weight function w;Let T be a subset of E that is included in some minimum spanning tree for G;Let (S, V - S) be any cut of G that respects T;Let (u, v) be a light edge crossing the cut (S, V-S). Then, edge (u, v) is a safe edge to be added to T.1701/14/19Proof of Theorem ILet T1 be an MST that contains T. To prove (u, v) is safe for T, it suffices to prove that there exists an MST T2 which contains (u, v)T.Case 1: (u, v) is also in T1. In this case, we can pick T2=T1 and we are done. Case 2: (u, v) is not in T1. Let (S, V-S) be the cut which respects T and for which (u, v) is a light