Bài giảng Cấu trúc Dữ liệu và giải thuật - Chương 7: Đồ thị - Nguyễn Thị Xuân Hương

Nội dung text: Bài giảng Cấu trúc Dữ liệu và giải thuật - Chương 7: Đồ thị - Nguyễn Thị Xuân Hương

1. Chương 7: ĐỒ THỊ 7.1. Giới thiệu -Trên thực tế, có nhiều bài toán liên quan tới một tập các đối tượng và những mối liên hệ giữa chúng, đòi hỏi toán học phải đặt ra một mô hình biểu diễn một cách chặt chẽ và tổng quát bằng ngôn ngữ ký hiệu, đó là đồ thị -Những ý tưởng cơ bản của nó được đưa ra từ thế kỷ XVIII bởi nhà toán học Thụy Sĩ Leonhard Euler, ông đã dùng mô hình đồ thị để giải bài toán về những cây cồng Konigsbeg nổi tiếng. -Mặc dù lý thuyết đồ thị đã được khoa học phát triển từ rất lâu nhưng lại có nhiều ứng dụng hiện đại. Đặc biệt là các thuật toán trên đồ thị đã có nhiều ứng dụng trên nhiều lĩnh vực khác nhau như: Mạng máy tính, Lý thuyết mã, Tối ưu hóa, kinh tế học, 1
2. Chương 7: ĐỒ THỊ 7.2. Một số định nghĩa và khái niệm 1.Định nghĩa Đồ thị: G = , trong đó: V là tập các đỉnh (Vertices) E: là tập các cạnh (Edges) VD: cạnh (u,v) với u, v là hai đỉnh của đồ thị •Phân loại đồ thị theo đặc tính và số lượng của tập cạnh E: -Đơn đồ thị: Nếu giữa hai đỉnh u,v của V có nhiều nhất là một cạnh trong E nối từ u đến v. -Đa đồ thị: Nếu giữa hai đỉnh u,v của V có nhiều hơn một cạnh trong E nối từ u đến v. -Đồ thị vô hướng (undirected graph): nếu các cạnh trong E không định hường: các cặp cạnh (u,v) = (v,u) 2
3. Chương 7: ĐỒ THỊ 2. Phân loại đồ thị theo đặc tính và số lượng của tập cạnh E: -Đơn đồ thị: Nếu giữa hai đỉnh u,v của V có nhiều nhất là một cạnh trong E nối từ u đến v. -Đa đồ thị: Nếu giữa hai đỉnh u,v của V có nhiều hơn một cạnh trong E nối từ u đến v. - Đồ thị vô hướng (undirected graph): các cạnh trong E không định hường: các cặp cạnh (u,v)≡(v,u) - Đồ thị có hướng (directed graph): các cạnh trong E có định hường: (u,v) ≠ (v,u) - Đồ thị có trọng số: mỗi cạnh của nó được gán tương ứng với một giá trị. 3
4. Chương 7: ĐỒ THỊ 7.2. Một số định nghĩa và khái niệm 3. Một số khái niệm: -Đỉnh kề, Cạnh liên thuộc: xét cạnh e  E, e = (u,v) thì ta nói hai đỉnh u,v kề nhau (adjacent) và cạnh e liên thuộc (incident) với đỉnh u và đỉnh v -Đường đi (path): đường đi có ộ dài p là một dãy: P=(v0, v1, vp) của các đỉnh sao cho (vi-1, vi) E. -Chu trình (circuit): là đường đi mà đỉnh bắt đầu và đỉnh kết thúc trùng nhau. -Đồ thị liên thông (connected): một đồ thị gọi là liên thông nếu mọi cặp đỉnh (u,v) ta đều có dường đi từ u đến v 4
5. Chương 7: ĐỒ THỊ 7.2. Một số định nghĩa và khái niệm 3. Một số khái niệm: -Đỉnh kề, Cạnh liên thuộc: xét cạnh e  E, e = (u,v) thì ta nói hai đỉnh u,v kề nhau (adjacent) và cạnh e liên thuộc (incident) với đỉnh u và đỉnh v -Đường đi (path): đường đi có ộ dài p là một dãy: P=(v0, v1, vp) của các đỉnh sao cho (vi-1, vi) E. -Chu trình (circuit): là đường đi mà đỉnh bắt đầu và đỉnh kết thúc trùng nhau. -Đồ thị liên thông (connected): một đồ thị gọi là liên thông nếu mọi cặp đỉnh (u,v) ta đều có dường đi từ u đến v 5
6. Chương 7: ĐỒ THỊ 7.3. Biểu diễn ồ thị trên máy tính 7.3.1. Ma trận kề: sử dụng một ma trận vuông cấp n •a[i,j]=1 nếu ( i, j) là cạnh thuộc E. •a[i,j]=0 nếu (i, j) không thuộc E. •Thảo luận: •- Khi đồ thị biểu diễn bằng ma trận kề có tính chất gì? •- Ưu nhược điểm gì ,khi nào thì sử dụng cách này? •- Khai báo dữ liệu và cài đặt thuật toán lưu trữ đồ thị. 6
7. Chương 7: ĐỒ THỊ 7.3. Biểu diễn đồ thị trên máy tính 7.3.1. Ma trận liên thuộc: sử dụng một ma trận [n,e] như sau: •a[i,j]=1 nếu đỉnh i thuộc cạnh j. •a[i,j]=0 nếu đỉnh i không thuộc cạnh j. Thảo luận: - Ưu nhược điểm gì khi biểu diễn bằng ma liên thuộc, khi nào thì sử dụng cách này? - Khai báo dữ liệu và cài đặt thuật toán lưu trữ? 7
8. Chương 7: ĐỒ THỊ 7.3. Biểu diễn ồ thị trên máy tính •7.3.3. Danh sách cạnh (edge list): Sử dụng danh sách liên kết gồm e nút tương ứng với e cạnh của đồ thị •Mỗi nút danh sách gồm có 3 trường •Ví dụ: Thảo luận: - Khi đồ thị biểu diễn bằng danh sách cạnh có tính chất gì? - Ưu nhược điểm gì? Khi nào thì sử dụng cách này? - Khai báo dữ liệu và cài đặt thuật toán lưu trữ đồ thị 8
9. Chương 7: ĐỒ THỊ 7.3. Biểu diễn ồ thị trên máy tính •7.3.3. Danh sách cạnh (edge list): Sử dụng danh sách liên kết gồm e nút tương ứng với e cạnh của đồ thị •Mỗi nút danh sách gồm có 3 trường •Ví dụ: Thảo luận: - Khi đồ thị biểu diễn bằng danh sách cạnh có tính chất gì? - Ưu nhược điểm gì? Khi nào thì sử dụng cách này? - Khai báo dữ liệu và cài đặt thuật toán lưu trữ đồ thị 9
10. Chương 7: ĐỒ THỊ 7.3. Biểu diễn ồ thị trên máy tính •7.3.3. Danh sách kề (adjacency list): Sử dụng n danh sách liên kết con (ứng với n đỉnh của đồ thị), mỗi danh sách chứa các đỉnh kề với đỉnh là số thứ tự của danh sách •Thảo luận: •- Ưu nhược điểm gì? khi nào thì sử dụng cách này? •- Khai báo dữ liệu và cài đặt thuật toán lưu trữ đồ thị 10
11. Chương 7: ĐỒ THỊ 7.4. Các phép duyệt đồ thị •Duyệt đồ thị: từ một đỉnh xuất phát, ta đi thăm các đỉnh còn lại của đồ thị, mỗi đỉnh duy nhất 1 lần. •Có hai phép duyệt: –Duyệt theo độ sâu Depth first search –Duyệt theo độ rộng: Breadth first search 11
12. Chương 7: ĐỒ THỊ 7.4.1. Duyệt đồ thị theo độ sâu: DFS Input: G = , đỉnh xuất phát v Output: các đỉnh được thăm. (cây khung bao trùm đồ thị) •Giải thuật: •B1: Thăm đỉnh xuất phát v •B2: Chọn một đỉnh kề với v, giả sử là u, nếu u chưa được thăm thì phép duyệt theo độ sâu được xuất phát từ u •Nếu tại một đỉnh v náo đó mà các đỉnh u kề với nó đã được thăm hết thì quay lại đỉnh đã thăm trước v để chọn các đỉnh kề khác chưa được thăm. 12
13. Chương 7: ĐỒ THỊ 7.4.1. Duyệt đồ thị theo độ sâu: DFS A VD: Duyệt đồ thị hình bên với đỉnh xuất phát A B C Thứ tự các đỉnh được thăm: A,B,C,E,F,D D E F 13
14. Chương 7: ĐỒ THỊ 7.4.1. Duyệt đồ thị theo độ sâu: DFS •Biểu diễn dữ liệu: •Đồ thị biểu diễn bằng ma trận kề hoặc danh sách kề #define MG 10 typedef struct GRAPH { int n; int E[MG][MG];} •Mảng Mark[n] với n = ||V||; Mark[i] = 0 -> đỉnh i chưa được thăm Mark[i] = 1 -> đỉnh i đã thăm •Khởi tạo, các phần tử Mark[i] = 0 với i = 1-> n; •Hàm visit(v): thăm đỉnh v; void visit( int v) { cout<<“ “ << v;} 14
15. Chương 7: ĐỒ THỊ 7.4.1. Duyệt đồ thị theo độ sâu: DFS Thủ tục: void DFS ( GRAPH G, int v) { visit(v); Mark [v] = 1; for mỗi u là đỉnh kề của v // for ( u =0; u<G.n; ++) if (G.E[u][v] ==1) if (Mark[u] == 0) DFS(u); } Độ phức tạp thuật toán: Biểu diễn bằng ma trận kề : O(n2) Biểu diễn bằng danh sách kề: O(n+e) 15
16. Chương 7: ĐỒ THỊ 7.4.1. Duyệt đồ thị theo độ sâu: DFS A Đồ thị Không liên thông: B CC G D E Void DepthFirstSearch (GRAPH G) { H F for mỗi đỉnh v thuộc G if ( v chưa thăm) DFS(v); } 16
17. Chương 7: ĐỒ THỊ 7.4.1. Duyệt đồ thị theo độ rộng: BFS Input: G = , đỉnh xuất phát v Output: cây bao trùm đồ thị theo độ rộng •Giải thuật: •B1: Thăm đỉnh xuất phát v •B2: Thăm các đỉnh kề w của v •B3: Thăm các đỉnh kề của các đỉnh w ở trên (nếu nó chưa được thăm) theo thứ tự đã thăm •Lặp lại B3 đến khi không còn đỉnh nào chưa được thăm. 17
18. Chương 7: ĐỒ THỊ 7.4.2. Duyệt đồ thị theo độ rộng: DFS A VD: Duyệt đồ thị hình bên với đỉnh xuất phát A B DC Thứ tự các đỉnh được thăm: A,B,C,D,E,F DC E F 18
19. Chương 7: ĐỒ THỊ 7.4.1. Duyệt đồ thị theo độ sâu: DFS •Biểu diễn dữ liệu: Biểu diễn dữ liệu: Đồ thị biểu diễn bằng ma trận kề hoặc danh sách kề. Mảng Mark[n] với n = ||V||; Mark[i] = 0 -> đỉnh i chưa được thăm Mark[i] = 1 -> đỉnh i đã thăm Khởi tạo, các phần tử Mark[i] = 0 với i = 1-> n; Sử dụng hàng đợi queue để lưu các đỉnh đã thăm.với các phép toán: Init(Q), Add(Q,x), Del(Q,y), Empty(Q) Hàm visit(v): thăm đỉnh v; • 19
20. Chương 7: ĐỒ THỊ 7.4.1. Duyệt đồ thị theo độ sâu: DFS void BFS ( GRAPH G, int v) { Init(Q); visit(v); Mark[v] =1; Add(Q,v) While (!Empty(Q)) { Del(Q,v); for mỗi w là đỉnh kề của v if (Mark[w] == 0) { visit(w); Mark[w] =1; Add(Q,w); } } } Độ phức tạp thuật toán: Biểu diễn bằng ma trận kề : O(n2) Biểu diễn bằng danh sách kề: O(n+e) 20
21. Chương 7: ĐỒ THỊ 7.4.2. Duyệt đồ thị theo độ rộng: BFS A Đồ thị Không liên thông: void BreadthFirstSearch (GRAPH G) B C { for mỗi đỉnh v thuộc G G D E if (v chưa thăm) BFS(v); } H F 21
22. Chương 7: ĐỒ THỊ 7.5. Một số giải thuật trên đồ thị 7.5.1. Bài toán cây khung có trọng số nhỏ nhất bao trùm đồ thị liên thông Input: Cho đồ thị G = liên thông có trọng số Output: Cây khung T= bao trùm đồ thị có trọng số nhỏ nhất. VD: Các cây khung của đồ thị G 22
23. Chương 7: ĐỒ THỊ 7.5.1. Cây khung có trọng số nhỏ nhất bao trùm đồ thị LT •Xây dựng cây khung •Thuật toán hợp nhất. -Mỗi đỉnh đồ thị coi là một cây. Nếu có cạnh nối hai cây khác nhau thì bổ sung cạnh đó vào cây cho đến khi đủ (n-1) cạnh là được. •Thuật toán áp dụng DFS và BFS. -Cả hai thuật toán đều duyệt mỗi đỉnh đúng một lần và nếu ta ghi dấu vết đi qua các cạnh nào thì bổ sung các cạnh đi qua đó là có được cây khung. •Một số giải thuật: Kruskal, PRIM 23
24. Chương 7: ĐỒ THỊ 7.5.1. Cây khung có trọng số nhỏ nhất bao trùm đồ thị LT • Giải thuật: Kruskal (1956) - dựa trên thuật toán hợp nhất Input: Cho đồ thị G = liên thông có trọng số Output: Cây khung T= bao trùm đồ thị có trọng số nhỏ nhất Giải thuật: Bước 1. Khởi tạo cây không có cạnh nào (chỉ gồm n đỉnh). Bước 2. Chọn cạnh có trọng số nhỏ nhất (cạnh đã chọn bị loại khỏi tập cạnh) Nếu thêm cạnh đó vào mà không tạo thành chu trình thì kết nạp cạnh đó vào cây. Bước 3. Lặp lại bước 2 cho đến khi đủ (n-1) cạnh. 24
25. Chương 7: ĐỒ THỊ 7.5.1. Cây khung có trọng số nhỏ nhất bao trùm đồ thị LT •Thủ tục: void Kruskal (GRAPH G, GRAPH &T) { T.V = G.V; T.E =  while(||T.E|| < n-1) { chọn cạnh (u,v) nhỏ nhất trong số các cạnh của G; G.E = G.E – (u,v); nếu (u,v) không tạo thành chu trình với T.E thì T.E = T.E+ (u,v); } } 25
26. Chương 7: ĐỒ THỊ 7.5.1. Cây khung có trọng số nhỏ nhất bao trùm đồ thị LT • Giải thuật: Kruskal (1956) •Nhận xét - Khi cài đặt cần sắp xếp danh sách cạnh theo thứ tự không giảm của trọng số. - Muốn thêm một cạnh (u,v) vào cây để không thành chu trình thì cạnh (u,v) phải nối hai cây khác nhau ( nếu cả u và v đều thuộc cùng một cây thì sẽ tạo thành chu trình). Như vậy ban đầu có n cây sau mỗi bước hợp nhất hai cây thành một cây. - Độ phức tạp phụ thuộc vào thuật toán sắp xếp danh sách cạnh, ví dụ sử dụng Heapsort có độ phức tạp là O(mlgn). 26
27. Chương 7: ĐỒ THỊ Giải thuật: PRIM Input:Cho đồ thị G = liên thông có trọng số, đỉnh xuất phát v Output: Cây khung T= bao trùm đồ thị có trọng số nhỏ nhất. Giải thuật: •Xét một cây T trong đồ thị G và một đỉnh v, gọi khoảng cách ngắn nhất từ v tới T là trọng số nhỏ nhất trong số các cạnh nối v với T: d[v] = min{ khoảng cách[u,v] với mọi u thuộc T} •Bước 1. Khởi tạo T chỉ gồm một đỉnh. •Bước 2. Chọn trong số các đỉnh gần T nhất và kết nạp đỉnh đó và cạnh có. khoảng cách ngắn nhất đó vào T. •Bước 3. Lặp lại bước 2 cho đến khi hoặc cây T là cây đã có đủ n đỉnh 27
28. Chương 7: ĐỒ THỊ Giải thuật: PRIM Thủ tục: void Prim (GRAPH G, GRAPH &T, int v) { T.V = T.V + {v}; G.V = G.V – v; T.E = ; while (|T.V| <n) { Chọn đỉnh u trong số các đỉnh gần T nhất - giả sử kề với w của câykhung T.V = T.V + {u}; G.V = G.V – {u}; T.E = T.E + {(u,w)}; } } 28
29. Chương 7: ĐỒ THỊ Giải thuật: PRIM •Nhận xét - Độ phức tạp thuật toán Prim là O(n2) - Có thể kết hợp thuật toán R. Prim với việc sử dụng cấu trúc Heap, khi đó độ phức tạp là O( (m+n)lgn) - Khi đồ thì dày thì nên dùng thuật toán R. Prim 29
30. Chương 7: ĐỒ THỊ 7.5.2. Bài toán về tìm đường đi giữa hai đỉnh bất kỳ của đồ thị Input: Đồ thị G= Output: Có đường đi giữa hai đỉnh bất kỳ của đồ thị không? Nhận xét về các phép toán logic trên ma trận Có Hai ma trận logic A[n][n], B[n][n]; Phép tuyển: C= A  B được xác định như sau : Cij = : Aij  Bij với 1<=i<=n ; 1<=j<=n ; Phép hộin : D = A  B được xác định như sau D (A  B ) • ij  ik kj với 1<=i<=n ; 1<=j<=n ; k 1 30
31. Chương 7: ĐỒ THỊ 7.5.2. Bài toán về tìm đường đi giữa hai đỉnh bất kỳ của đồ thị VD: Đồ thị G (hình bên) có ma trận biểu diễn: 1 2 3 4 1 0 1 1 0 2 1 0 1 0 Thực hiện phép hội hai ma trận: 3 1 1 0 1 4 0 0 1 0 A(2) = A  A A(3) = A A(2) A(4) = A A(3) 1 2 3 4 1 2 3 4 1 2 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 3 1 1 1 0 3 1 1 1 1 3 1 1 1 1 4 1 1 0 1 4 1 1 1 0 4 1 1 1 1 1 2 3 4 Vậy P = A  A(2)  A(3)  A(n) 1 1 1 1 1 2 1 1 1 1 P gọi là ma trận đường đi của G 3 1 1 1 1 4 1 1 1 1 31
32. Chương 7: ĐỒ THỊ 7.5.2. Bài toán về tìm đường đi giữa hai đỉnh bất kỳ của đồ thị A(2) = A  A 1 2 3 4 1 1 1 1 1 2 1 1 1 1 3 1 1 1 0 4 1 1 0 1 Thảo luận: (2) - A ij được xác định như thế nào?Bạn có nhận xét gì? - Xác định ma trận P như thế nào?Mỗi giá trị Pij = 1 cho biết điều gì? Nhận xét: - Đồ thị G’ biểu diễn tương ứng cho ma trận P là bao đóng truyền ứng của đồ thị G. - Giải thuật WarShall xác định ma trận đường đi P biểu diễn cho đồ thị G. 32
33. Chương 7: ĐỒ THỊ 7.5.2. Bài toán về tìm đường đi giữa hai đỉnh bất kỳ của đồ thị Giải thuật WarShall xác định ma trận đường đi P cho đồ thị G. Input: đồ thị biểu diễn bằng ma trận kề Output: Ma trận đường đi P void WarShall (int G[][] , int P[][]) { P = G; for(i = 0; i<n; i++) for ( j = 0; j <n; j++) for (k = 0; k < n; k++) P[i][j] = P[i][j] || P[i][k] && P [k][j]; } 33
34. Chương 7: ĐỒ THỊ 7.5.2. Bài toán về tìm đường đi giữa hai đỉnh bất kỳ của đồ thị •Nhận xét: giải thuật warshall cho ta biết: - giữa hai đỉnh của đồ thị G có thể có 1 hoặc nhiều đường đi hoặc không - Nếu có nhiều đường đi thì đường đi nào là ngắn nhất Bài toán tìm đường đi ngắn nhất giữa hai đỉnh của đồ thị. Giải thuật Floyd, Dijkstra 34
35. Chương 7: ĐỒ THỊ 7.5.2. Bài toán về tìm đường đi giữa hai đỉnh bất kỳ của đồ thị Giải thuật Dijkstra: Bài toán: Input: Đồ thị có trọng số G= Cho một đỉnh xuất phát s, và đỉnh kết thúc t Output: Có đường đi ngắn nhất từ đỉnh s đến t không? Nếu có thì độ dài của đường đi là bao nhiêu? Ma trận trọng số D được xác định: D[i,j]= trọng số của cạnh (i,j). D[i,i]=0 với mọi đỉnh. D[I, j]= một số nào đó để đánh dấu là không có cạnh (i,j) chẳng hạn. +∞ 35
36. Chương 7: ĐỒ THỊ 7.5.2. Bài toán về tìm đường đi giữa hai đỉnh bất kỳ của đồ thị Giải thuật: Giả thiết, tất cả các trọng số các cạnh đều không âm. Sử dụng phương pháp gán nhãn cho mỗi đỉnh của đồ thị: -d[v]: nhãn tại đỉnh v chứa độ dài của đường đi ngắn nhất từ đỉnh xuất phát tới v -Khởi tạo ban đầu với mọi đỉnh v của G: D[v] = Cost(s,v); -Gọi S là tập chứa tất cả các đỉnh mà đường đi ngắn nhất đi qua. => Cần xây dựng S từng bước cho đến khi S chứa đỉnh kết thúc. -Khởi tạo ban đầu S rỗng. -Sử dụng một nhãn đánh dấu P[v] với P[v] = w (w là đỉnh mà đường ngắt nhất từ đỉnh xuất phát đi qua w rồi đến v) -Ban đầu, với mỗi v thuộc G, P[v] = s ( s là đỉnh xuất phát) 36
37. Chương 7: ĐỒ THỊ 7.5.2. Bài toán về tìm đường đi giữa hai đỉnh bất kỳ của đồ thị Giải thuật: B1: Khởi tạo: Mọi v thuộc G: d[v] = Cost(s,v); p[v] = s; S = S+{s}; //s là đỉnh xuất phát B2: Lặp quá trình sau (khi S chưa gồm đỉnh k.thúc) 1.Chọn đỉnh v có d[v] nhỏ nhất trong các đỉnh còn lại (thuộc V-S) đưa đỉnh v vào tập S: S = S + {v}; 2. Sau khi tập các đỉnh có đường đi ngắn nhất đi qua chứa thêm v -> xét các đỉnh w còn lại, nếu đường đi ngắn nhất đến nó đi qua v mà ngắn hơn đường đi hiện tại -> gán lại nhãn bằng đường đi này, và nhãn đánh dấu để đi đến w đi trực tiếp qua v theo công thức: nếu d[v] + Cost(v,w) < d[w] thì d[w] = d[v] + Cost(v,w) ; và p[w] = p[v]; 37
38. Chương 7: ĐỒ THỊ 7.5.2. Bài toán về tìm đường đi giữa hai đỉnh bất kỳ của đồ thị Giải thuật: B1: Khởi tạo: Mọi v thuộc G: d[v] = Cost(s,v); p[v] = s; S = S+{s}; //s là đỉnh xuất phát B2: Lặp quá trình sau (khi S chưa gồm đỉnh k.thúc) 1.Chọn đỉnh v có nhãn d[v] nhỏ nhất ( v thuộc V-S) S = S + {v}; 2. Xét w thuộc V-S Nếu d[v] + Cost(v,w) < d[w] thì gán lại nhãn: d[w] = d[v] + Cost(v,w) ; và p[w] = p[v]; 38
39. Chương 7: ĐỒ THỊ void Dijkstra (int c[][], int s, int t, int &d[], int &p[]) { S = S+ {s}; // s là đỉnh xuất phát for ( v =0; v<n; i++) { d[v] = Cost(s,v); p[v] = s;} while (S chưa gồm đỉnh kết thúc t) { với mỗi v thuộc tập V-S // V là tập đỉnh của G chọn v có d[v] nhỏ nhất S = S + {v]; với mỗi w còn lại (mark[w] = 0) nếu d[v] + Cost(v,w) < d[w] { d[w] = d[v] + Cost(v,w) ; và p[w] = p[v];} } } - độ phức tạp thuật toán là O(n2) 39
40. Chương 7: ĐỒ THỊ 7.5.2. Bài toán về tìm đường đi giữa hai đỉnh bất kỳ của đồ thị Khai báo dữ liệu: Int c[20][20]; Int d[20], p[20]; Sử dụng mảng đánh dấu: int Mark[20]; Khởi tạo: Mark [i] = 0 với mọi i=1, n-1]; n là số đỉnh của G Với Mark [i] = 0 -> i thuộc G Nếu Mark [i] ==1 -> i thuộc tập S Viết chương trình? 40