MIT OpenCourseWare http ocw mit edu 6 006 Introduction to Algorithms Spring 2008 For information about citing these materials or our Terms of Use visit http ocw mit edu terms Lecture 12 Searching I Graph Search Representations 6 006 Spring 2008 Lecture 12 Searching I Graph Search and Representations Lecture Overview Search 1 of 3 Graph Search Applications Graph Representations Introduction to breadth rst and depth rst search Readings CLRS 22 1 22 3 B 4 Graph Search Explore a graph e g nd a path from start vertices to a desired vertex Recall graph G V E V set of vertices arbitrary labels E set of edges i e vertex pairs v w ordered pair directed edge of graph unordered pair undirected e g a b c d V a b c d E a b a c b c b d c d V a b c E a c b c c b b a a b c DIRECTED UNDIRECTED Figure 1 Example to illustrate graph terminology 1 Lecture 12 Searching I Graph Search Representations 6 006 Spring 2008 Applications There are many web crawling How Google nds pages social networking Facebook friend nder computer networks Routing in the Internet shortest paths next unit solving puzzles and games checking mathematical conjectures Pocket Cube Consider a 2 2 2 Rubik s cube Figure 2 Rubik s Cube Con guration Graph vertex for each possible state edge for each basic move e g 90 degree turn from one state to another undirected moves are reversible Puzzle Given initial state s nd a path to the solved state vertices 8 38 264 539 520 because there are 8 cubelets in arbitrary positions and each cubelet has 3 possible twists Figure 3 Illustration of Symmetry 2 Lecture 12 Searching I Graph Search Representations 6 006 Spring 2008 can factor out 24 fold symmetry of cube x one cubelet 811 3 7 37 11 022 480 in fact graph has 3 connected components of equal size only need to search in one 7 36 3 674 160 3 Lecture 12 Searching I Graph Search Representations 6 006 Spring 2008 Geography of con guration graph possible first moves breadthfirst tree reachable in two steps but not one Figure 4 Breadth First Tree reachable con gurations distance 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 90 turns 1 6 27 120 534 2 256 8 969 33 058 114 149 360 508 930 588 1 350 852 782 536 90 280 276 diameter 3 674 160 90 180 turns 1 9 54 321 1 847 9 992 50 136 227 536 870 072 1 887 748 623 800 2 644 diameter 3 674 160 Wikipedia Pocket Cube Cf 3 3 3 Rubik s cube 1 4 trillion states diameter is unknown 26 4 Lecture 12 Searching I Graph Search Representations 6 006 Spring 2008 Representing Graphs data structures Adjacency lists Array Adj of V linked lists for each vertex u V Adj u stores u s neighbors i e v V u v E are just outgoing edges if directed See Fig 5 for an example colorBlue u v in Python Adj dictionary of list set values vertex any hashable object e g int tuple advantage multiple graphs on same vertices a b c a c b c c b Adj Figure 5 Adjacency List Representation Object oriented variations object for each vertex u u neighbors list of neighbors i e Adj u Incidence Lists can also make edges objects see Figure 6 u edges list of outgoing edges from u advantage storing data with vertices and edges without hashing 5 a Lecture 12 Searching I Graph Search Representations e a e 6 006 Spring 2008 e b Figure 6 Edge Representation Representing Graphs contd The above representations are good for for sparse graphs where E V 2 This translates to a space requirement V E Don t bother with s inside O Adjacency Matrix assume V 1 2 v number vertices A aij V V matrix where i row and j column and aij 1 if i j E otherwise See Figure 7 good for dense graphs where E V 2 space requirement V 2 cool properties like A2 gives length 2 paths and Google PageRank A but we ll rarely use it Google couldn t V 20 billion 50 000 petabytes 1 a A b c 2 3 0 0 1 1 0 1 0 1 0 1 2 3 Figure 7 Matrix Representation 6 V 2 4 1020 Lecture 12 Searching I Graph Search Representations 6 006 Spring 2008 Implicit Graphs Adj u is a function or u neighbors edges is a method no space just what you need now High level overview of next two lectures Breadth rst search Levels like geography s frontier Figure 8 Illustrating Breadth First Search frontier current level initially s repeatedly advance frontier to next level careful not to go backwards to previous level actually nd shortest paths i e fewest possible edges Depth rst search This is like exploring a maze e g left hand rule See Figure 9 follow path until you get stuck backtrack along breadcrumbs until you reach an unexplored edge 7 Lecture 12 Searching I Graph Search Representations recursively explore it careful not to repeat a vertex s Figure 9 Illustrating Depth First Search 8 6 006 Spring 2008
View Full Document
Unlocking...