ADA減治法減常數(shù)規(guī)模算法II

1、2022-3-2212022-3-222Decrease and Conquer(V)Chapter 5l The application of DFSl Breadth-First Search Algorithm (BFS)2022-3-223Goals of this lecturebAt the end of this lecture, you should : Master topological sort, know how to find the topological order of a graph (if exist) Master the idea of breadth-

2、first search algorithm, analyze its time complexity, solve other real problems by BFS Master the comparision between DFS and BFS2022-3-224DFS and Topological Sort bA topological sort of a directed acyclic graph G = (V, E) is a linear ordering of all its vertices such that if G contains an edge (u, v

3、), then u appears before v in the ordering.132421342022-3-225Applications of Topological SortbA general life-related applicationdressing orderGraph AlgorithmsData StructureJava LanguageAdvanced MathematicsGraph TheorybAssembly lines in industriesbCourses arrangement in schools2022-3-226The Algorithm

4、 Time Complexity Analysis: Line 1: (|V| +|E|) Line 2: (|V|) Line 3: (1)TopologicalSort(G)/Input: A directed acyclic graph G = (V, E)/Output: A topological order of all the vertices of G1 call DFS(G) to compute finishing times postnu for each vertex u2 as each vertex is finished, insert it into the f

5、ront of a linked list3 return the linked list of vertices2022-3-227Getting DressedUnderwearSocksShoesPantsBeltShirtWatchTieJacket2022-3-228Getting DressedUnderwearSocksShoesPantsBeltShirtWatchTieJacket123456789Socks9/9Underwear6/8Pants7/7Shoes8/6Watch5/5Shirt1/4Belt4/3Tie2/2Jacket3/1/4/2/1/3/5/8/7/6

6、/92022-3-229bNote: We only introduce BFS for undirected graphs. But it also works for directed graphs. Archetype for Prims minimum-spanning-tree algorithm Archetype for Dijkstras single-source shortest-paths algorithmBreadth-first Search (outline)wThe idea of BFSwThe single source shortest-paths pro

7、blem for unweighted graphwThe Breadth-first search algorithmwThe running time of BFS algorithm2022-3-2210The Breadth-First SearchbThe idea of the BFS:Visit the vertices as follows:w Visit all vertices directly connected to starting vertexw Visit all vertices that are two edges away from the starting

8、 vertexw Visit all vertices that are three edges away from the starting vertex1. 2022-3-2211The Single Source Shortest-paths ProblembThe problem: Input: A graph G = (V, E) and a source vertex sV Output: A shortest path from s to each vertex v V and the distance dv Where distance dv: The length of th

9、e shortest path from s to v. For example dc=2. Define ds=0ebdsac2022-3-2212What does the BFS do?bGiven a graph G = (V, E), the BFS returns: The shortest distance dv from s to v The predecessor or parent v, which is used to derive a shortest path from s to vertex v.bIn addition to the two arrays dv a

10、nd v, BFS also uses another array colorv, which has three possible values: WHITE: represented “undiscovered” vertices; GRAY: represented “discovered” but not “processed” vertices; BLACK: represented “processed” vertices. 2022-3-2213The Breadth-First Search AlgorithmbG is given by its adjacency-lists

11、.bInitialization: First Part: lines 1 4 Second Part: lines 5 - 9bMain Part: lines 10 18bEnqueue(Q, v): add a vertex v to the end of the queue QbDequeue(Q): Extract the first vertex in the queue Q 2022-3-2214Example of Breadth-First Searchbgiven the undirected graph below and the source vertex s, fin

12、d the distance dv from s to each vertex v V, and the predecessor v by the algorithm described earlier.bsdcafe2022-3-2215Example (Continued)bInitializationvertex u s a b c d e fcoloruduu GWWWWWW 0 NILNIL NILNILNILNILNILQ = (put s into Q (discovered),mark s gray (unprocessed)bsdcafe02022-3-2216Example

13、 (continued)bWhile loop, first iteration Dequeue s from Q. Find adjs= Mark b, e as “G” Update db, de, b, e Put b, e into Q Mark s as “B”bQ= bsdcafe011vertex u s a b c d e fcoloruduu GWWWWWW 0 1 1 NILNIL sNILNIL sNIL2022-3-2217Example (continued)bWhile loop, second iteration Dequeque b from Q, find a

14、djb= Mark a, c, f as “G”, Update da, dc, df, a, c, f Put a, c, f into Q Mark b as “B”bQ=2bsdcafe01122vertex u s a b c d e fcoloruduu GWWWWWW 0 2 1 2 1 2NIL b s bNIL s b2022-3-2218Example (continued)bWhile loop, third iteration Dequeque e from Q, find adje= Mark d as “G”, mark e as “B” Update dd, d,

15、Put d into Q bQ=bsdcafe0112222vertex u s a b c d e fcoloruduu GWWWWWW 0 2 1 2 2 1 2NIL b s b e s b2022-3-2219Example (continued)bWhile loop, fourth iteration Dequeque a from Q, find adja= mark a as “B”bQ=bsdcafe0112222vertex u s a b c d e fcoloruduu GWWWWWW 0 2 1 2 2 1 2NIL b s b e s b2022-3-2220Exa

16、mple (continued)bWhile loop, fifth iteration Dequeque c from Q, find adjc= mark c as “B”bQ=bsdcafe0112222vertex u s a b c d e fcoloruduu GWWWWWW 0 2 1 2 2 1 2NIL b s b e s b2022-3-2221Example (continued)bWhile loop, sixth iteration Dequeque f from Q, find adjf= mark f as “B”bQ=22bsdcafe0112222vertex

17、 u s a b c d e fcoloruduu GWWWWWW 0 2 1 2 2 1 2NIL b s b e s b2022-3-2222Example (continued)bWhile loop, seventh iteration Dequeque d from Q, find adjd= mark d as “B”bQ is empty22bsdcafe0112222vertex u s a b c d e fcoloruduu GWWWWWW 0 2 1 2 2 1 2NIL b s b e s b2022-3-2223Example (continued)bWhile lo

18、op, eighth iterationbSince Q is empty, stop22bsdcafe0112222vertex u s a b c d e fcoloruduu GWWWWWW 0 2 1 2 2 1 2NIL b s b e s b2022-3-2224Example (continued)Question:How do you construct a shortestpath from s to any vertexby using the following table?22bsdcafe0112222vertex u s a b c d e fcoloruduu G

19、WWWWWW 0 2 1 2 2 1 2NIL b s b e s b2022-3-2225bGiven a vertex v, the procedure Print-Path(G, s, v) prints a path from s to v.Print-Path(G,s,v)/ print the shortest path from s to vif v=s print selse if v = Nil print “no path from s “to” v existselse Print-Path(G, s, v) print vThe Answer2022-3-2226Ana

20、lysis of the BFS Algorithmu = every vertex, but only once (Why?)3(|V|-1)53|V|+266deg(u)+2(6deg( )2)u Vu2022-3-2227bHence, T(V, E) = O(|E|).( ,)(3| 2)(6deg( )2)u VT V EVu( ,)(3| 2)(12| 2|)5| 12| 2(|)T V EVEVVEO VE Analysis of the BFS Algorithm (cont.)bHence the total amount of time needed for process

21、ing all the vertices is at most bSo, we get: bRemark: since G is connected, we have |E|=|V|-1.2022-3-2228bAn old world puzzle: A peasant finds himself on a riverbank with a wolf, a goat and a head of cabbage. He needs to transport all three to the other side of the river in his boat. However, the boat has room for only the peasant himself and one other item (either the wolf, the goat, or the cabbage). In his absence, the wolf would eat the goat, and the goat would eat the cabbage. S