Bài giảng Toán rời rạc - Bài 17: Tìm kiếm trên đồ thị (Version 0.4) - Trần Vĩnh Đức

Tìm kiếm trên đồ thị (Version 0.4) Trần Vĩnh Đức HUST Ngày 29 tháng 7 năm 2018 1 / 57 Tài liệu tham khảo ▶ S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Algorithms, July 18, 2016. ▶ Chú ý: Nhiều hình vẽ trong tài liệu được lấy tùy tiện mà chưa xin phép. 2 / 57 Nội dung Biểu diễn đồ thị Tìm kiếm theo chiều sâu trên đồ thị vô hướng Tìm kiếm theo chiều sâu trên đồ thị có hướng Thành phần liên thông mạnh Biểu diễn đồ thị dùng Ma trận kề Nếu đồ thị có n = |V| đỉnh v1, v2, . . . , vn, thì ma trận kề là một mảng n× n với phần tử (i, j) của nó là aij = { 1 nếu có cạnh từ vi tới vj 0 ngược lại. Ví dụ v1 v2 v3 A = 1 1 10 0 1 0 1 0  4 / 57 Dùng ma trận kề có hiệu quả? ▶ Có thể kiểm tra có cạnh nối giữa cặp đỉnh bất kỳ chỉ cần một lần truy cập bộ nhớ. ▶ Tuy nhiên, không gian lưu trữ là O(n2) 5 / 57 Biểu diễn đồ thị dùng danh sách kề ▶ Dùng một mảng Adj gồm |V| danh sách. ▶ Với mỗi đỉnh u ∈ V, phần tử Adj[u] lưu trữ danh sách các hàng xóm của u. Có nghĩa rằng: Adj[u] = {v ∈ V | (u, v) ∈ E}. Ví dụ 0 1 2 Adj[0] = {0, 1, 2} Adj[1] = {2} Adj[2] = {1} 6 / 57 Dùng danh sách kề có hiệu quả? ▶ Có thể liệt kê các đỉnh kề với một đỉnh cho trước một cách hiệu quả. ▶ Nó cần không gian lưu trữ là O(|V|+ |E|). Ít hơn O(|V|2) rất nhiều khi đồ thị ít cạnh. 7 / 57 Nội dung Biểu diễn đồ thị Tìm kiếm theo chiều sâu trên đồ thị vô hướng Tìm kiếm theo chiều sâu trên đồ thị có hướng Thành phần liên thông mạnh ptg12441863 Adjacency-lists data structure. 4HESTANDARDGRAPHREPRESENTATIONFORGRAPHSTHATARE NOT DENSE IS CALLED THEadjacency-lists data structureWHEREWE KEEP TRACK OF ALL THE VERTICESADJACENTTOEACHVERTEXONALINKEDLISTTHATISASSOCIATEDWITHTHATVERTEX7E MAINTAINANARRAYOFLISTSSOTHATGIVENAVERTEXWECANIMMEDIATELYACCESSITSLIST4O IMPLEMENTLISTSWEUSEOURBag!$4FROMSection 1.3WITHALINKED LISTIMPLEMENTA- TIONSOTHATWECANADDNEWEDGESINCONSTANTTIMEANDITERATETHROUGHADJACENTVERTI- CESINCONSTANTTIMEPERADJACENTVERTEX4HEGraphIMPLEMENTATIONONPAGEISBASED ONTHISAPPROACHANDTHElGUREONTHEFACINGPAGEDEPICTSTHEDATASTRUCTURESBUILTBY THISCODEFORtinyG.txt4OADDANEDGECONNECTINGv and w, we add w to vSADJACENCY list and v to wSADJACENCYLIST4HUSEACHEDGEAPPEARStwiceINTHEDATASTRUCTURE4HIS GraphIMPLEMENTATIONACHIEVESTHEFOLLOWINGPERFORMANCECHARACTERISTICS n 3PACEUSAGEPROPORTIONALTOV + E n #ONSTANTTIMETOADDANEDGE n 4IMEPROPORTIONALTOTHEDEGREEOFvTOITERATETHROUGHVERTICESADJACENTTOv CONSTANTTIMEPERADJACENTVERTEXPROCESSED 4HESECHARACTERISTICSAREOPTIMALFORTHISSETOFOPERATIONSWHICHSUFlCEFORTHEGRAPH PROCESSINGAPPLICATIONSTHATWECONSIDER0ARALLELEDGESANDSELF LOOPSAREALLOWEDWE DONOTCHECKFORTHEM Note)TISIMPORTANTTOREALIZETHATTHEORDERINWHICHEDGES AREADDEDTOTHEGRAPHDETERMINESTHEORDERINWHICHVERTICESAPPEARINTHEARRAYOF ADJACENCY LISTS BUILT BYGraph-ANY DIFFERENT AR- RAYSOFADJACENCYLISTSCANREPRESENTTHESAMEGRAPH 7HENUSINGTHECONSTRUCTORTHATREADSEDGESFROM ANINPUTSTREAMTHISMEANSTHATTHEINPUTFORMAT AND THE ORDER INWHICH EDGES ARE SPECIlED IN THE lLE DETERMINE THE ORDER INWHICH VERTICES APPEAR INTHEARRAYOFADJACENCYLISTSBUILTBYGraph3INCE OURALGORITHMSUSEadj()ANDPROCESSALLADJACENT VERTICESWITHOUTREGARDTOTHEORDERINWHICHTHEY APPEAR IN THE LISTS THIS DIFFERENCE DOES NOT AFFECT THEIR CORRECTNESS BUT IT IS IMPORTANT TOBEAR IT IN MINDWHENDEBUGGING OR FOLLOWING TRACES 4O FA- CILITATETHESEACTIVITIESWEASSUMETHATGraphHASA TESTCLIENTTHATREADSAGRAPHFROMTHEINPUTSTREAM NAMEDASCOMMAND LINEARGUMENTANDTHENPRINTS ITRELYINGONTHEtoString() IMPLEMENTATIONON PAGE TOSHOWTHEORDERINWHICHVERTICESAP- PEARINADJACENCYLISTSWHICHISTHEORDERINWHICH ALGORITHMSPROCESSTHEMSEEExercise 4.1.7  13 13 0 5 4 3 0 1 9 12 6 4 5 4 0 2 11 12 9 10 0 6 7 8 9 11 5 3 % java Graph tinyG.txt 13 vertices, 13 edges 0: 6 2 1 5 1: 0 2: 0 3: 5 4 4: 5 6 3 5: 3 4 0 6: 0 4 7: 8 8: 7 9: 11 10 12 10: 9 11: 9 12 12: 11 9 tinyG.txt Output for list-of-edges input V E first adjacent vertex in input is last on list second representation of each edge appears in red 5254.1 n Undirected Graphs Câu hỏi Từ một đỉnh của đồ thị ta có thể đi tới những đỉnh nào? 9 / 57 Tìm đường trong mê cung P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch03 GTBL020-Dasgupta-v10 August 10, 2006 19:18 Chapter 3 Algorithms 83 Figure 3.2 Exploring a graph is rather like navigating a maze. A C B F D H I J K E G L H G DA C F K L J I B E 3.2 Depth-first search in undirected graphs 3.2.1 Exploring mazes Depth-first search is a surprisingly versatile linear-time procedure that reveals a wealth of information about a graph. The most basic question it addresses is, What parts of the graph are reachable from a given vertex? To understand this task, try putting yourself in the position of a computer that has just been given a new graph, say in the form of an adjacency list. This representation offers just one basic operation: finding the neighbors of a vertex. With only this primitive, the reachability problem is rather like exploring a labyrinth (Figure 3.2). You start walking from a fixed place andwhenever you arrive at any junction (vertex) there are a variety of passages (edges) you can follow. A careless choice of passages might lead you around in circles or might cause you to overlook some accessible part of the maze. Clearly, you need to record some intermediate information during exploration. This classic challenge has amused people for centuries. Everybody knows that all you need to explore a labyrinth is a ball of string and a piece of chalk. The chalk prevents looping, by marking the junctions you have already visited. The string always takes you back to the starting place, enabling you to return to passages that you previously saw but did not yet investigate. How can we simulate these two primitives, chalk and string, on a computer? The chalk marks are easy: for each vertex, maintain a Boolean variable indicating whether it has been visited already. As for the ball of string, the correct cyber- analog is a stack. After all, the exact role of the string is to offer two primitive operations—unwind to get to a new junction (the stack equivalent is to push the new vertex) and rewind to return to the previous junction (pop the stack). Instead of explicitly maintaining a stack, we will do so implicitly via recursion (which is implemented using a stack of activation records). The resulting algorithm Hình: Tìm kiếm trên đồ thị cũng giống tìm đường trong mê cung 10 / 57 procedure explore(G, v) Input: đồ thị G = (V,E); v ∈ V Output: visited(u)=true với mọi đỉnh u có thể đến được từ v visited(v) = true previsit(v) for each edge (v, u) ∈ E: if not visited(u): explore(G, u) postvisit(v) 11 / 57 Ví dụ: Kết quả chạy explore(G,A) P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch03 GTBL020-Dasgupta-v10 August 10, 2006 19:18 Chapter 3 Algorithms 83 Figure 3.2 Exploring a graph is rather like navigating a maze. A C B F D H I J K E G L H G DA C F K L J I B E 3.2 Depth-first search in undirected graphs 3.2.1 Exploring mazes Depth-first searchis a surprisingly versatile linear-time procedure that reveals a wealth of information about a graph. The most basic question it addresses is, What parts of the graph are reachable from a given vertex? To understand this task, try putting yourself in the position of a computer that has just been given a new graph, say in the form of an adjacency list. This representation offers just one basic operation: finding the neighbors of a vertex. With only this primitive, the reachability problem is rather like exploring a labyrinth (Figure 3.2). You start walking from a fixed place andwhenever you arrive at any junction (vertex) there are a variety of passages (edges) you can follow. A careless choice of passages might lead you around in circles or might cause you to overlook some accessible part of the maze. Clearly, you need to record some intermediate information during exploration. This classic challenge has amused people for centuries. Everybody knows that all you need to explore a labyrinth is a ball of string and a piece of chalk. The chalk prevents looping, by marking the junctions you have already visited. The string always takes you back to the starting place, enabling you to return to passages that you previously saw but did not yet investigate. How can we simulate these two primitives, chalk and string, on a computer? The chalk marks are easy: for each vertex, maintain a Boolean variable indicating whether it has been visited already. As for the ball of string, the correct cyber- analog is a stack. After all, the exact role of the string is to offer two primitive operations—unwind to get to a new junction (the stack equivalent is to push the new vertex) and rewind to return to the previous junction (pop the stack). Instead of explicitly maintaining a stack, we will do so implicitly via recursion (which is implemented using a stack of activation records). The resulting algorithm P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch03 GTBL020-Dasgupta-v10 August 10, 2006 19:18 Chapter 3 Algorithms 85 Figure 3.4 The result of explore(A) on the graph of Figure 3.2. I E J C F B A D G H For instance, while B was being visited, the edge B − E was noticed and, since E was as yet unknown, was traversed via a call to explore(E ). These solid edges form a tree (a connected graph with no cycles) and are therefore called tree edges. The dotted edges were ignored because they led back to familiar terrain, to vertices previously visited. They are c lled back edges. 3.2.2 Depth-first search The explore procedure visits only the portion of the graph reachable from its starting point. To examine the rest of the graph, we need to restart the procedure elsewhere, at some vertex that has not yet been visited. The algorithm of Figure 3.5, called depth-first search (DFS), does this repea edly until the entire graph h been traversed. Figure 3.5 Depth-first search. procedure dfs(G) for all v ∈ V: visited(v) = false for all v ∈ V: if not visited(v): explore(v) The first step in analyzing the running time of DFS is to observe that each vertex is explore’d just once, thanks to the visited array (the chalk marks). During the exploration of a vertex, there are the following steps: 1. Some fixed amount of work—marking the spot as visited, and the pre/postvisit. 12 / 57 Tìm kiếm theo chiều sâu procedure dfs(G) for all v ∈ V: visited(v) = false for all v ∈ V : if not visited(v): explore(G, v) 13 / 57 Ví dụ: Đồ thị và Rừng DFS P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch03 GTBL020-Dasgupta-v10 August 10, 2006 19:18 86 3.2 Depth-first search in undirected graphs 2. A loop in which adjacent edges are scanned, to see if they lead somewhere new. This loop takes a different amount of time for each vertex, so let’s consider all vertices together. The total work done in step 1 is then O(|V |). In step 2, over the course of the entire DFS, each edge {x, y} ∈ E is examined exactly twice, once during explore(x) and once during explore(y). The overall time for step 2 is therefore O(|E |) and so the depth-first search has a running time of O(|V | + |E |), linear in the size of its input. This is as efficient as we could possibly hope for, since it takes this long even just to read the adjacency list. Figure 3.6 (a) A 12-node graph. (b) DFS search forest. (a) A B C D E F G H I J K L (b) A B E I J G K FC D H L 1,10 2,3 4,9 5,8 6,7 11,22 23,24 12,21 13,20 14,17 15,16 18,19 Figure 3.6 shows the outcome of depth-first search on a 12-node graph, once again breaking ties alphabetically (ignore the pairs of numbers for the time being). The outer loop of DFS calls explore three times, on A, C , and finally F . As a result, there are three trees, each rooted at one of these starting points. Together they constitute a forest. 3.2.3 Connectivity in undirected graphs An undirected graph is connected if there is a path between any pair of vertices. The graph of Figure 3.6 is not connected because, for instance, there is no path from A to K . However, it does have three disjoint connected regions, corresponding to the following sets of vertices: {A, B, E , I , J } {C , D,G , H, K , L} {F }. These regions are called connected components: each of them is a subgraph that is internally connected but has no edges to the remaining vertices. When explore is started at a particular vertex, it identifies precisely the connected component containing that vertex. And each time the DFS outer loop calls explore, a new connected component is picked out. 14 / 57 Bài tập Xây dựng rừng DFS cho đồ thị sau với các đỉnh lấy theo thứ tự từ điển. Vẽ cả những cạnh nét đứt. 15 / 57 Rừng DFS và số thành phần liên thông P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch03 GTBL020-Dasgupta-v10 August 10, 2006 19:18 86 3.2 Depth-first search in undirected graphs 2. A loop in which adjacent edges are scanned, to see if they lead somewhere new. This loop takes a different amount of time for each vertex, so let’s consider all vertices together. The total work done in step 1 is then O(|V |). In step 2, over the course of the entire DFS, each edge {x, y} ∈ E is examined exactly twice, once during explore(x) and once during explore(y). The overall time for step 2 is therefore O(|E |) and so the depth-first search has a running time of O(|V | + |E |), linear in the size of its input. This is as efficient as we could possibly hope for, since it takes this long even just to read the adjacency list. Figure 3.6 (a) A 12-node graph. (b) DFS search forest. (a) A B C D E F G H I J K L (b) A B E I J G K FC D H L 1,10 2,3 4,9 5,8 6,7 11,22 23,24 12,21 13,20 14,17 15,16 18,19 Figure 3.6 shows the outcome of depth-first search on a 12-node graph, once again breaking ties alphabetically (ignore the pairs of numbers for the time being). The outer loop of DFS calls explore three times, onA, C , and finallyF . As a result, there are three trees, each rooted at one of these starting points. Together they constitute a forest. 3.2.3 Connectivity in undirected graphs An undirected graph is connected if there is a path between any pair of vertices. The graph of Figure 3.6 is not connected because, for instance, there is no path from A to K . However, it does have three disjoint connected regions, corresponding to the following sets of vertices: {A, B, E , I , J } {C , D,G , H, K , L} {F }. These regions are called connected components: each of them is a subgraph that is internally connected but has no edges to the remaining vertices. When explore is started at a particular vertex, it identifies precisely the connected component containing that vertex. And each time the DFS outer loop calls explore, a new connected component is picked out. v ccnum[v] A 1 B 1 C 2 D 2 E 1 F 3 G 2 H 2 I 1 J 1 Biến ccnum[v] để xác định thành phần liên thông của đỉnh v. 16 / 57 Tính liên thông trong đồ thị vô hướng procedure dfs(G) cc = 0 for all v ∈ V: visited(v) = false for all v ∈ V: if not visited(v): cc = cc + 1 explore(G, v) procedure explore(G, v) visited(v) = true previsit(v) for each edge (v, u) ∈ E: if not visited(u): explore(G, u) postvisit(v) procedure previsit(v) ccnum[v] = cc 17 / 57 Bài tập Hãy cài đặt chương trình tìm số thành phần liên thông của một đồ thị vô hướng. 18 / 57 previsit và postvisit ▶ Lưu thời gian lần đầu đến đỉnh trong mảng pre ▶ Lưu thời gian lần cuối rời khỏi đỉnh trong mảng post ▶ Để tính hai thông tin này ta dùng một bộ đếm clock, khởi tạo bằng 1, và được cập nhật như sau: procedure previsit(v) pre[v] = clock clock = clock + 1 procedure postvisit(v) post[v] = clock clock = clock + 1 19 / 57 Bài tập Vẽ rừng DFS với cả số pre và post cho mỗi đỉnh cho đồ thị sau. 20 / 57 Tính chất của previsit và postvisit Mệnh đề Với mọi đỉnh u và v, hai khoảng [ pre(u), post(u) ] và [ pre(v), post(v) ] ▶ hoặc là rời nhau, ▶ hoặc là có một khoảng chứa một khoảng khác. Tại sao? vì [ pre(u), post(u) ] là khoảng thời gian đỉnh u nằm trong ngăn xếp. Cấu trúc vào-sau, ra-trước đảm bảo tính chất này. 21 / 57 Nội dung Biểu diễn đồ thị Tìm kiếm theo chiều sâu trên đồ thị vô hướng Tìm kiếm theo chiều sâu trên đồ thị có hướng Thành phần liên thông mạnh Bài tập Hãy vẽ rừng DFS với số pre và post trên mỗi đỉnh cho đồ thị có hướng sau. P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch03 GTBL020-Dasgupta-v10 August 10, 2006 19:18 88 3.3 Depth-first search in directed graphs Figure 3.7 DFS on a directed graph. AB C F DE G H A H B C E D F G 12,15 13,14 1,16 2,11 4,7 5,6 8,9 3,10 In further analyzing the directed case, it helps to have terminology for important relationships between nodes of a tree. A is the root of the search tree; everything else is its descendant. Similarly, E has descendants F , G , and H , and conversely, is an ancestor of these three nodes. The family analogy is carried further: C is the parent of D, which is its child. For undirected graphs we distinguished between tree edges and nontree edges. In the directed case, there is a slightly more elaborate taxonomy: B ac k Forw ard Cross Tr ee A B C D DFS tree Tree edges are actually part of the DFS forest. Forward edges lead from a node to a nonchild descendant in the DFS tree. Back edges lead to an ancestor in the DFS tree. Cross edges lead to neither descendant nor ancestor; they therefore lead to a node that has already been completely explored (that is, already postvisited). Figure 3.7 has two forward edges, two back edges, and two cross edges. Can you spot them? Ancestor and descendant relationships, as well as edge types, can be read off directly from pre and post numbers. Because of the depth-first exploration strategy, vertex u is an ancestor of vertex v exactly in those cases where u is discovered first and 23 / 57 Lời giải P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch03 GTBL020-Dasgupta-v10 August 10, 2006 19:18 88 3.3 Depth-first search in directed graphs Figure 3.7 DFS on a directed graph. AB C F DE G H A H B C E D F G 12,15 13,14 1,16 2,11 4,7 5,6 8,9 3,10 In further analyzing the directed case, it helps to have terminology for important relationships between nodes of a tree. A is the root of the search tree; everything else is its descendant. Similarly, E has descendants F , G , and H , and conversely, is an ancestorof the e three nodes. The family analogy is carried further: C is the parent of D, which is its child. For undirected graphs we distinguished between tree edges and nontree edges. In the directed case, there is a slightly more elaborate taxonomy: B ac k Forw ard Cross Tr ee A B C D DFS tree Tree edges are actually part of the DFS forest. Forward edges lead from a node to a nonchild descendant in the DFS tree. Back edges lead to an ancestor in the DFS tree. Cross edges lead to neither descendant nor ancestor; they therefore lead to a node that has already been completely explored (that is, already postvisited). Figure 3.7 has two forward edges, two back edges, and two cross edges. Can you spot them? Ancestor and descendant relationships, as well as edge types, can be read off directly from pre and post numbers. Because of the depth-first exploration strate