15.082J, 6.855J, and ESD.78JSept 16, 2010Lecture 3. Graph SearchBreadth First SearchDepth First SearchIntro to program verificationTopological Sort2OverviewToday: Different ways of searching a graph a generic approach breadth first search depth first search program verification data structures to support network search topological order Fundamental for most algorithms considered in this subject3Searching a Directed GraphALGORITHM SEARCH INPUT: A directed network G, and node sOUTPUT: The set S = {j : there is a directed path from s to j in G}. These are the nodes reachable from s. For each node j ∈ S\s, pred(j) is a node that precedes j on some path from s; e.g. (pred(2) = 1, pred(8) = 412453 697812453 6978Marked nodes, admissible arcsA node is either marked or unmarked. Initially only node s is marked. If a node is marked, it is reachable from node s.An arc (i,j) ∈ A is admissible if node i is marked and j is not.412453 697812453 6978Marked nodesAdmissible arcs5Scanning arcs12 531235CurrentArc(1) CurrentArc(1) CurrentArc(1)Scan through the arc list for the selected node, and keep track using current arc. Stop when an admissible arc is identified or when the arc list is fully scanned6Algorithm SearchInitialize as follows: unmark all nodes in N;mark node s;pred(s) = 0; {that is, it has no predecessor}LIST = {s} while LIST ≠ ø doselect a node i in LIST;if node i is incident to an admissible arc (i,j) thenmark node j;pred(j) := i;add node j to the end of LIST;else delete node i from LIST The algorithm in the book also keeps track of the order in which nodes are marked.Breadth first search7It is a breadth first search (bfs) if the selected node is the first node on LIST. Breadth First Search Animation8More on Breadth First SearchTheorem. The breadth first search tree is the “shortest path tree”, that is, the path from s to j in the tree has the fewest possible number of arcs.1 23212453 6978110215346867969933The numbers next to the nodes are the distances from node 1.Depth first search9It is a depth first search (dfs) if the selected node is the last node on LIST. Depth First Search Animation10132 9875486796542 31The depth first search treeNote that each induced subtree has consecutively labeled nodes.(The descendents are visited in order.)Algorithm AnalysisHow does one prove that an algorithm is correct?How does one prove that it terminates in finite time?How does one obtain a tight upper bound on running time?11Some useful approachesSubdivide the algorithm into “chunks”.Invariants: properties that are true throughout the running of the algorithmThings that change: functions that increase monotonically every time the algorithm reenters the same loop. 1213Algorithm SearchInitialize while LIST ≠ ø doselect a node i in LIST;if node i is incident to an admissible arc (i,j) thenmark node j;pred(j) := i;add node j to the end of LIST;else delete node i from LIST loop14Algorithm InvariantsSelect Node 2LIST1 2 4 85 6 9 7875312453 697811122122484488454566569697977996655442Invariants: whenever control of the program is at loop:1.Any marked node is reachable from s.2.All nodes on LIST are marked.3.If a marked node j is not on LIST, then A(j) has been fully scanned.Proving the correctness of the invariantsAn Important step in proving algorithm correctness: Prove that the algorithm invariants are true using induction. • Prove that they are true after the initialization• Assuming that they are true at the beginning of the k-th iteration of the while loop, prove that they are true at the beginning of the subsequent iteration of the while loop. 15Things that change and proof of finitenessThings that change between successive times that the control of the program is at loop:1. Either a new node is marked and added to LIST, or a new node is fully scanned and deleted from LIST.16Number of iterations of while loop is at most 2n.Therefore the algorithm terminates in O(n) calls of the “while loop.”Proof of CorrectnessThe algorithm terminates when LIST = ∅.17Let S = marked nodes.Let T = unmarked nodes.1245 t6s3s5426STThen no arc (i,j) is directed from S to T. Otherwise, by Invariant 2, j would have been marked when (i, j) was scanned.By invariant 1, all nodes in S are reachable from s.By invariant 3, all arcs out of S have been scanned.Therefore, no node in T is reachable from s.18Cutset TheoremCorollary of algorithm’s correctness. There is no directed path from s to t if and only if the following is true: there is a partition of the node set N into subsets S and T = N - S such that there is no arc directed from a node in S to a node in T.SsTtRunning time analysis19Initialize. while LIST ≠ ø doselect a node i in LIST;if node i is incident to an admissible arc (i,j) thenmark node j;pred(j) := i;add node j to the end of LIST;else delete node i from LIST loopTotal time spent in while loop (other than arc scans)• O(1) time per loop• < 2n iterations of the loop• O(n) time in totalTotal time spent in scanning arcs• O(1) time per arc scanned• m arcs• O(m) time in total.Running time: O(n + m)20Initialize Initializebeginunmark all nodes in N;mark node s;pred(s) = 0; {that is, it has no predecessor}LIST = {s}endUnmarking takes O(n)All else takes O(1)21Theorem. Algorithm search determines all nodes reachable from node s in O(n + m) time.All U.S. Presidents have worn glassesTrueNo President (before Obama) has been an only childTrueNo President was a bachelorFalse. James Buchanan was a bachelor.George Washington grew marijuana on his Plantation.True Mental BreakGeorge Washington’s false teeth were made of wood.False. They were made of whale bone.Three of the first 10 Presidents died on July 4.True. Thomas Jefferson, John Adams, James MonroeJohn Quincy Adams kept a pet alligator in the East Room of the White HouseTrue. Calvin Coolidge believed that the world was flat.False. But Andrew Jackson did.Mental Break24Finding all connected components in an undirected graphBreadth first search will find a connected component of an undirected graph in time proportional to the number of arcs in the component. (A component of an undirected graph is a maximally connected subgraph.)To find all components: Maintain a set U of unmarked nodes. • Delete a node from U after it is marked.• After each component is searched, select a node of U and begin a search. • Running time O(1) per selection and deletionComp 1Comp 2Comp 325Proof of