Graphs and Graph Algorithms Graphs are a pervasive data structure Trees are a special form of graphs connected and without a cycle Graph Representations adjacency matrix adjacency list list of edges Graph Algorithms Searching a graph using BFS and DFS MST and shortest paths Topological order 01 14 19 1 Representation of Graphs Mathematical set representation G V E where V v1 v2 vn E e1 e2 em and ek vi vj Adjacency Matrix Adjacency lists consist of an array of n lists one for each vertex in V for each u V u adj stores a pointer to the linked list that contains the set v u v E 01 14 19 1 2 3 4 5 6 1 2 3 4 5 6 2 5 6 5 6 4 5 2 Representation of Graphs We 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 01 14 19 1 2 weight of this edge 1 4 weight of this edge 2 5 weight of this edge 3 5 weight of this edge 3 6 weight of this edge 4 5 weight of this edge 6 6 weight of this edge 3 Equivalence of Graph Representations Each 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 01 14 19 4 Minimum Spanning Tree Problem A 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 4 a 11 8 01 14 19 8 b h 2 7 i 1 7 c 4 6 g d 14 2 f weighted graph 9 4 e 10 b a 8 2 i h 1 7 c d e 4 g 9 2 f A Minimum Spanning Tree 5 Kruskal s MST Algorithm This 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 do 3 Make Set v 4 sort edges of E in order by non decreasing weight 5 for each edge u v E G do 6 01 14 19 Running time is O E lg E if Find Set u Find Set v then 7 T T u v T is set of edges 8 Union u v 9 return T union by rank takes O lg E set of vertices 6 Example of Kruskal s MST Algorithm 4 a 11 8 h 4 b a 11 8 4 a 01 14 19 h 4 b 11 h i g 8 i g 1 8 i g 1 8 c 2 7 i 1 7 4 6 2 7 g 2 4 e a 11 10 8 h d 9 4 b e a 11 f 10 8 d 9 4 e a 10 8 d 9 4 14 f e 10 a g i g 1 8 i g 1 8 b i 1 7 4 6 g e f 10 d 9 e f 10 d 9 e 14 2 c 2 7 7 4 6 9 14 2 c 2 7 7 4 6 d 14 2 c 2 7 4 6 8 h h i 1 b 11 8 7 7 c 2 h 11 f 8 b f 14 4 6 9 14 2 c 2 7 7 4 6 d 14 2 c 2 7 4 6 1 b 8 8 7 7 c 2 h 11 a 8 b f 10 d 9 14 2 f e 10 7 Prim s MST Algorithm This 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 Q v key if there is no edge from v to any vertices in V Q Other fields of a vertex include u Pointer to its parent predecessor u adj adjacent vertex set to u It starts from any vertex r V Q Q r u v x 01 14 19 8 Prim s MST Algorithm MST Prim G V E W r 1 2 Q V for each vertex u Q do 3 u key 4 u nil 5 6 r key 0 decrease key operation while Q do 7 u Extract Min Q 8 for each vertex v u adj do 9 10 01 14 19 11 O V 2 E if v Q and w u v v key then v u v key w u v decrease key O lg V 9 Prim s MST Algorithm Running Time 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 and there are two vertices in each edge The total running time is then calculated as follows 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 01 14 19 O E lg E O E lg V 10 Example of Prim s MST Algorithm 4 0 a 11 8 8 b 2 7 h a 11 8 7 h 11 8 8 01 14 19 i 1 7 c 4 6 g e f 10 d 9 e 10 d 9 f a b c d e f g h i 0 Initialize 1 5 Q f 14 2 Q 9 14 2 8 2 7 h g 8 b 7 4 6 1 4 a i d 14 2 c 2 8 4 g 8 b 4 6 1 4 4 i 7 c b c d e f g h i 4 8 Iteration 1 7 11 Q e 10 c d e f g h i 8 8 Iteration 2 7 11 11 4 4 a b 11 8 7 2 h 4 a 7 2 h 4 a 7 2 h 4 a 01 14 19 2 h 1 c 7 g 6 2 8 2 c i 7 4 g 2 2 8 2 c i 1 2 4 6 8 b 11 i 1 7 4 8 8 b 11 g 2 7 4 6 1 7 4 i 8 b 11 c 2 1 8 4 8 8 7 4 g 6 2 7 d 9 f 4 i e 14 10 7 d f 4 10 f 4 e 10 f 4 h 2 7 4 8 e g h 4 …
View Full Document
Unlocking...