6.006- Introduction to Algorithms Lecture 12 – Graph Algorithms Prof. Manolis Kellis CLRS 22.2-22.3Combinatorics Ponytail)No)ponytail)Beard&Erik&?&No&Beard&Piotr&Manolis&Unit #4 – Games, Graphs, Searching, Networks 3Unit #4 Overview: Searching Today: Introduction to Games and Graphs • Rubik’s cube, Pocket cube, Game space • Graph definitions, representation, searching Tuesday: Graph algorithms and analysis • Breadth First Search, Depth First Search • Queues, Stacks, Augmentation, Topological sort Thursday: Networks in biology and real world • Network/node properties, metrics, motifs, clusters • Dynamic processes, epidemics, growth, resilienceLast time: Games and GraphsPocket Cube • 2 × 2 × 2 Rubik’s cube • Start with any colors • Moves are quarter turns of any face • “Solve” by making each side one colorSearching for a solution path • Graph algorithms allow us explore space – Nodes: configurations – Edges: moves between them – Paths to ‘solved’ configuration: solutions 1 turn 6 neighbors 27 two-away How big is the space?Graphs • V={a,b,c,d} • E={{a,b}, {a,c}, {b,c}, {b,d}, {c,d}} • V = {a,b,c} • E = {(a,c), (a,b) (b,c), (c,b)} a c dba b c • G=(V,E) • V a set of vertices Usually number denoted by n • E ⊆ V × V a set of edges (pairs of vertices) Usually number denoted by m Note m ≤ n(n-1) = O(n2) Undirected example Directed exampleGraph Representation • Adjacency lists • Incidence lists • Adjacency matrix • Implicit representation a b c c c / b / b / a b c (a,c) (a,b) / (b,c) / (c,b) / a (1) b (2) c (3) 0 1 1 a)(1))0 0 1 b (2))0 1 0 c (3))Neighbors(a)&&[c,b]&Neighbors(b)&&[b]&Neighbors(c)&&[b]&a&b& c&Today: Searching graphs &?&Searching Graph • We want to get from current Rubik state to “solved” state • How do we explore?Breadth First Search • start with vertex v • list all its neighbors (distance 1) • then all their neighbors (distance 2) • etc. • algorithm starting at s: define frontier F initially F={s} repeat F=all neighbors of vertices in F until all vertices foundDepth First Search • Like exploring a maze • From current vertex, move to another • Until you get stuck • Then backtrack till you find a new place to explore • “left-hand” rule • Exploring a mazeHow to handle cycles: BFS/DFS • What happens if unknowingly revisit a vertex? Will eventually happen if graph contains a cycle • BFS: get wrong notion of distance • DFS: may get in circles • Solution: mark vertices BFS: if you’ve seen it before, ignore DFS: if you’ve seen it before, back upBreadth First Search (BFS)BFS algorithm outline • Initial vertex s Level 0 • For i=1,… grow level i Find all neighbors of level i-1 vertices (except those already seen) i.e. level i contains vertices reachable via a path of i edges and no fewer Level&1&Level&2&Level&3&s&v&BFS example a c v x z s d f 1122 2 3 3 0s&a&x&z&d&c&f&BFS algorithm outline • Initial vertex s Level 0 • For i=1,… grow level i Find all neighbors of level i-1 (except those already seen) i.e. level i contains vertices reachable via a path of i edges and no fewer • Where can the other edges of the graph be? They cannot jump a layer (otherwise v would be in Level 2) But they can be between nodes in same or adjacent levels Level&1&Level&2&Level&3&s&v&The ‘frontier’ of BFS exploration a c v x z s d f 1122 2 3 3 0s&a&x&z&d&c&f&The&only&edges&¬&traversed&by&BFS&&link&verHces&&within&the&same&level&BFS Algorithm • BFS(V,Adj,s) level={s: 0}; parent = {s: None}; i=1 frontier=[s] #previous level, i-1 while frontier next=[] #next level, i for u in frontier for v in Adj[u] if v not in level #not yet seen level[v] = i #level of u+1 parent[v] = u next.append(v)&frontier = next i += 1&BFS Analysis: Runtime • Naïve analysis: outer loop |V| * inner loop |V| • Vertex v appears at the frontier at most once Since then it has a level And nodes with a level aren’t added again Total time spent adding nodes to frontier O(n) • Adj[v] only scanned once Just when v is in frontier Total time ∑v|| Adj[v] || • This sum counts each “outgoing” edge • So O(m) time spend scanning adjacency lists • Total: O(m+n) time --- “Linear time” For sparse graphs |V|+|E| is much better than |V|2BFS Analysis: Correctness • Claim: If there is a path of L edges from s to v, then v is added to next when i=L or before • Proof: induction Base case: s is added before setting i=1 Inductive step when i=L: • Consider path of length L from s to v • This must contain: (1) a path of length L-1 from s to u • (2) and an edge (u,v) from u to v By inductive hypothesis, u was added to next when i=L-1 or before • If v has not already been inserted in next before i=L, then it gets added during the scan of Adj[u] at i=L So it happens when i=L or before. QED i.e. why are all nodes reachable from s explored? (we’ll actually prove a stronger claim)Corrollary: BFSShortest Paths • From correctness analysis, conclude more: Level[v] is length of shortest sv path • Parent pointers form a shortest paths tree i.e. the union of shortest paths to all vertices • To find shortest path from s to v Follow parent pointers from v backwards Will end up at sDepth First Search (DFS)DFS Algorithm Outline • Explore a maze Follow path until you get stuck Backtrack along breadcrumbs till find new exit i.e. recursively exploreDFS Algorithm • parent = {s: None} • call DFS-visit (V, Adj, s) def DFS-visit (V, Adj, u) for v in Adj[u] if v not in parent #not yet seen parent[v] = u DFS-visit (V, Adj, v) #recurse!DFS example run (starting from s) s&1&(in&tree)&2&(in&tree)&3&(in&tree)&5&(forward&edge)&a&b&c&s&a&b&c&d&7&(cross&edge)&d&DFS Runtime Analysis • Quite similar to BFS • DFS-visit only called once per vertex v Since next time v is in parent set • Edge list of v scanned only
View Full Document
Unlocking...