Slide 1GraphsExamplesPocket CubeRepresentationExampleSearching GraphBreadth First SearchDepth First SearchProblem: CyclesSlide 11OutlineExampleOutlineExampleAlgorithmAnalysis: RuntimeAnalysis: CorrectnessShortest PathsSlide 20OutlineAlgorithmDemo (from s)Runtime AnalysisCorrectness?Edge ClassificationTradeoffs6.006- Introduction to AlgorithmsLecture 12Prof. Constantinos DaskalakisCLRS 22.2-22.3Graphs•G=(V,E)•V a set of verticesUsually number denoted by n•E Í V ´ V a set of edges (pairs of vertices)Usually number denoted by mNote m ≤ n(n-1) = O(n2)•Flavors:Pay attention to order of vertices in edge: directed graphIgnore order: undirected graph•Then only n(n-1)/2 possible edgesExamples•Undirected•V={a,b,c,d}•E={{a,b}, {a,c}, {b,c}, {b,d}, {c,d}}•Directed•V = {a,b,c}•E = {(a,c), (a,b) (b,c), (c,b)} abcdabcPocket Cube•2 ´ 2 ´ 2 Rubik’s cube•Configurations are adjacent, if one can be obtained from the other by quarter turns•Basic Question: is solved state reachable with such moves from the starting state?Representation•To solve graph problems, must examine graph•So need to represent in computer•Four representations with pros/consAdjacency lists (of neighbors of each vertex)Incidence lists (of edges from each vertex)Adjacency matrix (of which pairs are adjacent)Implicit representation (as neighbor function)ExampleabcCb/b/c/acbSearching 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.Depth 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 exploreProblem: Cycles•What happens if unknowingly revisit a vertex?•BFS: get wrong notion of distance•DFS: may get in circles•Solution: mark verticesBFS: if you’ve seen it before, ignoreDFS: if you’ve seen it before, back upBreadth First Search (BFS)Outline•Initial vertex sLevel 0•For i=1,… grow level iFind 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 fewerLevel 1Level 2Level 3svExampleacvxzs df11222330saxzdcfOutline•Initial vertex sLevel 0•For i=1,… grow level iFind 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?Only between nodes in same or adjacent levelsLevel 1Level 2Level 3svExampleacvxzs df11222330saxzdcfAlgorithm•BFS(V,Adj,s)level={s: 0}; parent = {s: None}; i=1frontier=[s] #previous level, i-1while frontiernext=[] #next level, ifor u in frontierfor v in Adj[u] if v not in level #not yet seenlevel[v] = i #level of u+1parent[v] = unext.append(v)frontier = nexti += 1Analysis: Runtime•Vertex v appears at the frontier at most onceSince then it has a levelAnd nodes with a level aren’t added againTotal time spent adding nodes to frontier O(n)•Adj[v] only scanned onceJust when v is in frontierTotal 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”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: inductionBase case: s is added before setting i=1Path of length L from s to v path of length L-1 from s to u, and edge (u,v)By induction, add u when i=L-1 or beforeIf v has not already been inserted in next before i=L, it gets added when scan u at i=LSo it happens when i=L or beforei.e. why are all nodes reachable from s explored?Shortest Paths•From correctness analysis, conclude more:Level[v] is length of shortest s—v path•Parent pointers form a shortest paths treeWhich is union of shortest paths to all vertices•To find shortest path, follow parent pointersWill end up at sDepth First Search (DFS)Outline•Explore a mazeFollow path until you get stuckBacktrack along breadcrumbs till find new exiti.e. recursively exploreAlgorithm•parent = {s: None}•call DFS-visit (V, Adj, s)Routine DFS-visit (V, Adj, u)for v in Adj[u]if v not in parent #not yet seenparent[v] = uDFS-visit (V, Adj, v) #recurse!Demo (from s)s1 (in tree)2 (in tree)3 (in tree)4 (back edge)5 (forward edge)abcsabcd7 (cross edge)6 (in tree)dRuntime Analysis•Quite similar to BFS•DFS-visit only called once per vertex vSince next time v is in parent set•Edge list of v scanned only once (in that call)•So time in DFS-visit is 1/vertex + 1/edge•So time is O(n+m)Correctness?•Trickier than BFS•Can use induction on length of shortest path from starting vertexInduction Hypothesis: “each vertex at distance k is visited”Induction Step: •Suppose vertex v at distance k•Then some u at distance k-1 with edge (u,v)•u is visited (by induction hypothesis)•Every edge out of u is checked•If v wasn’t previously visited, it gets visited from uEdge Classification•Tree edge used to get to new child•Back edge leads from node to ancestor in tree•Forward edge leads to descendant in tree•Cross edge leads to a different subtree•To label what edge is of what type, keep global time counter and store interval during which vertex is on recursion stackCross edgeForward edgeBack edgetree edgeTradeoffs•Solving Rubik’s cube?BFS gives shortest solution•Robot exploring a building?Robot can trace out the exploration pathJust drops markers behind•Only difference is “next vertex” choiceBFS uses a queueDFS uses a stack
View Full Document
Unlocking...