Giáo trình Cấu trúc dữ liệu và giải thuật (Bản đẹp)

trỏ, trỏ tới cây con trái của nút 
 D E G 
đó 
 Trường right ứng với con 
trỏ, trỏ tới cây con phải của Hình 6.8 
nút đó 
 Ta có thể khai báo như sau: 
 Type 
 item = ...;{kiểu dữ liệu của các nút trên cây } 
 Tree = ^Node; 
 Node = record 
 Giáo trình Cấu trúc dữ liệu và giải thuật Trang 81 / 92 
 info : item; 
 left, right: Tree; 
 end; 
 var Root :Tree; 
 Ví dụ: cây nhị phân hình 5.8 có dạng lưu trữ móc nối như ở hình 5.9 
 Root 
 A 
 B C 
 D E G 
 Hình 6.9. Cấu trúc dữ liệu biểu diễn cây 
 Để truy nhập vào các nút trên cây cần có một con trỏ Root, trỏ tới nút gốc 
của cây 
2.2. Biểu diễn cây tổng quát 
 Biểu diễn cây tổng quát bằng một cây nhị phân gọi là cây nhị phân tương 
đương. 
 Với cách biểu diễn này chúng ta gán số thứ tự cho các cây con của mỗi 
nút.Giả sử trên hình vẽ ta đánh số thứ tự từ trái sang phải. 
 Chẳng hạn với nút có 5 cây con sau đây,thì sẽ đánh số như 
 A 
 B C D E F 
 1 2 3 4 5 
 HÌNH 6.10 
 Chúng ta xem: nút 1 là “con cả“ của nút A, nút 2 là “em kề nút 1”.,nút 3 là 
“em kề nút 2” v.v. Với mỗi nút chúng ta chỉ cần chú ý tới hai quan hệ này là 
đủ 
 Từ đó quy cách của mỗi nút trên cây nhị phân tương đương, có dạng : 
 LCC INFO REK 
 Giáo trình Cấu trúc dữ liệu và giải thuật Trang 82 / 92 
 Với LCC là trường con trỏ, ở đó chứa địa chỉ của nút “con cả” 
 REK là trường con trỏ, ở đó chứa địa chỉ của nút “em kề nó” 
 Như vậy với bất kì một cây con nào cũng có một và chỉ một cây nhị phân 
tương đương với nó. Điều đó cũng có nghĩa là : với một cây tổng quát cho, thì 
biểu diễn trong máy của nó là cây nhị phân tương đương. Các phép xử lí trên 
cây tổng quát đều thực hiện qua cây nhị phân tương đương này và kết quả sau 
khi chuyển đổi lại. sẽ phải khớp với ý đồ xử lí đối với cây tổng quát. 
 Sau đây là ví dụ minh họa một vài cây nhị phân tương đương ứng với cây 
tổng quát cho: 
 T T’ 
 A A 
 B 
 B C D 
 E F G H I J K E C 
 T F G D 
 T’ 
 A 
 H 
 A 
 B C B I 
 D C J 
 D E F G 
 E F K 
 H I J 
 H G 
 K 
 I J 
 K 
 T là con trỏ,Trỏ tới gốc cây tổng quát 
 T’ là con trỏ, trỏ tới gốc cây nhị phân tương đương 
 của cây T) 
 HÌNH 6.11 
 Ta thấy : 
 - Gốc của cây nhị phân tương đương T’ không có con phải. 
 Giáo trình Cấu trúc dữ liệu và giải thuật Trang 83 / 92 
 - Cây nhị phân tương đương T’ của một cây nhị phân T thường khác nó. 
3. Bài toán duyệt cây nhị phân 
 Phép xử lý các nút trên cây - mà ta gọi chung là phép thăm các nút một 
cách hệ thống, sao cho mỗi nút được thăm đúng một lần, gọi là phép duyệt cây. 
Chúng ta thường duyệt cây nhị phân theo một trong ba thứ tự: duyệt trước, duyệt 
giữa và duyệt sau, các phép này được định nghĩa đệ qui như sau: 
3.1. Duyệt theo thứ tự trước (gốc – trái – phải) 
 - Thăm gốc A 
 - Duyệt câycon trái theo thứ trước 
 - Duyệt cây con phải theo thư tự trước 
 B C 
 Cài đặt: 
 procedure Truoc(Root : Tree); D E F 
 Begin 
 if Root nil then G 
 Begin H 
 write(Root^.info); 
 Truoc(Root^.left); HÌNH 6.12 
 Truoc(Root^.right); 
 end; 
 end; 
 Ví dụ: Chúng ta duyệt trước với cây ở hình 5.12, có kết quả như sau: 
 A B D C E G H F 
3.2. Duyệt theo thứ tự giữa (trái – gốc – phải) 
 - Duyệt câycon trái theo thứ giữa 
 - Thăm gốc 
 - Duyệt cây con phải theo thư tự giữa 
 Cài đặt: 
 procedure Giua(Root : Tree); 
 Begin 
 if Root^.left nil then 
 Begin 
 Preorder(Root^.left); 
 Giáo trình Cấu trúc dữ liệu và giải thuật Trang 84 / 92 
 write(Root^.info); 
 Preorder(Root^.right); 
 end; 
 end; 
 Ví dụ: Chúng ta duyệt trước với cây ở hình 5.12, có kết quả như sau: 
 D B A G H E C F 
3.3. Duyệt theo thứ tự sau (trái – phải – gốc) 
 - Duyệt câycon trái theo thứ sau 
 - Duyệt cây con phải theo thư tự sau 
 - Thăm gốc 
 Cài đặt: 
 procedure Sau(Root : Tree); 
 Begin 
 if Root^.right nil then 
 Begin 
 Preorder(Root^.left); 
 Preorder(Root^.right); 
 write(Root^.info); 
 end; 
 end; 
 Ví dụ: Chúng ta duyệt trước với cây ở hình 5.12, có kết quả như sau: 
 D B H G E F C A 
Bài tập thực hành của học viên 
 6.1. Trình bày các biểu thức theo thứ tự duyệt trước, duyệt sau, duyệt giữa 
của cây sau: 
 A 
 B J 
 I K D F 
 H L Y 
 6.2. Dựng cây nhị phân biết thứ tự các đỉnh khi duyệt theo 
Giáo trình Cấu trúc dữ liệu và giải thuật Trang 85 / 92 
a. Thứ tự trước: A D F G H K L P Q R W Z 
 Thứ tự giữa : G F H K D L A W R Q P Z 
b. Theo thứ tự sau: F G H D A L P Q R Z W K 
 Thứ tự giữa : G F H K D L A W R Q P Z 
YÊU CẦU VỀ ĐÁNH GIÁ KẾT QUẢ HỌC TẬP: 
 Kết quả Kết qủa 
 Tiêu chí đánh giá Hệ số 
 thực hiện học tập 
 Kiến thức 0,3 
 Kỹ năng 0,5 
 Thái độ 0,2 
 Cộng: 
 Giáo trình Cấu trúc dữ liệu và giải thuật Trang 86 / 92 
 CHƯƠNG 7: ĐỒ THỊ 
 Mã chương: Mh17-07 
 Giới thiệu: 
 Đồ thị có vai trò rất quan trọng trong thực tế. Đồ thị được dùng để giải 
 các bài toán trong nhiều lĩnh vực khác nhau. Ví dụ, dùng đồ thị để biểu diễn 
 các mạch điện, biểu diễn các công thức phân tử hóa học, biểu diễn mạng máy 
 tính. Đồ thị với các trọng số được gán cho các cạnh của nó có thể dùng để 
 giải các bài toán như bài toán tìm đường đi ngắn nhất giữa hai thành phố 
 trong một mạng giao thông. Chúng ta cũng có thể dùng đồ thị để lập lịch thi 
 và phân chia kênh cho các đài truyền hình. 
 Mục tiêu: 
 - Trình bày được khái niệm về đồ thị; 
 - Cài đặt được đồ thị trên máy tính bằng các cấu trúc mảng và cấu trúc danh 
sách liên kết; 
 - Giải được bài toán tìm đường đi trên đồ thị. 
 - Thực hiện các thao tác an toàn với máy tính. 
 Nội dung gồm: 
1.Các định nghĩa 
 Một đồ thị G bao gồm một tập hợp V các đỉnh và một tập hợp E các cung, 
ký hiệu G=(V,E). Các đỉnh còn được gọi là nút (node). Các cung nối giữa hai 
đỉnh, hai đỉnh này có thể trùng nhau. 
 Hai đỉnh có cung nối nhau gọi là hai đỉnh kề (adjacency). 
 Một cung nối giữa hai đỉnh v, w có thể coi như là một cặp điểm (v,w). Nếu 
cặp này có thứ tự thì ta có cung có thứ tự, ngược lại thì cung không có thứ tự. 
 Nếu các cung trong đồ thị G có thứ tự thì G gọi là đồ thị có hướng (directed 
graph). 
 Nếu các cung trong đồ thị G không có thứ tự thì đồ thị G là đồ thị vô hướng 
(undirected graph). 
 Trong các phần sau này ta dùng từ đồ thị (graph) để nói đến đồ thị nói 
chung, khi nào cần phân biệt rõ ta sẽ dùng đồ thị có hướng, đồ thị vô hướng. 
 Thông thường trong một đồ thị, các đỉnh biểu diễn cho các đối tượng còn 
các cung biểu diễn mối quan hệ (relationship) giữa các đối tượng đó. Chẳng hạn 
các đỉnh có thể biểu diễn cho các thành phố còn các cung biểu diễn cho đường 
giao thông nối giữa hai thành phố. 
 Một đường đi (path) trên đồ thị là một dãy tuần tự các đỉnh v1, v2,..., vn 
sao cho (vi,vi+1) là một cung trên đồ thị (i=1,...,n-1). Đường đi này là đường đi 
 Giáo trình Cấu trúc dữ liệu và giải thuật Trang 87 / 92 
từ v1 đến vn và đi qua các đỉnh v2,...,vn-1. Đỉnh v1 còn gọi là đỉnh đầu, vn gọi là 
đỉnh cuối. Độ dài của đường đi này bằng (n-1). Trường hợp đặc biệt dãy chỉ có 
một đỉnh v thì ta coi đó là đường đi từ v đến chính nó có độ dài bằng không. 
 Đường đi gọi là đơn (simple) nếu mọi đỉnh trên đường đi đều khác nhau, 
ngoại trừ đỉnh đầu và đỉnh cuối có thể trùng nhau. Một đường đi có đỉnh đầu và 
đỉnh cuối trùng nhau gọi là một chu trình (cycle). Một chu trình đơn là một 
đường đi đơn có đỉnh đầu và đỉnh cuối trùng nhau và có độ dài ít nhất là 1. 
 Trong nhiều ứng dụng ta thường gắn các giá trị (value) vào các cung thể 
hiện một thông tin liên quan tới cung đó, giá trị đó được gọi là trọng số, lúc này 
ta nói đồ thị có trọng số. 
 Đồ thị con của một đồ thị G=(V,E) là một đồ thị G'=(V',E') trong đó: 
 ¾ V’⊆V và 
 ¾ E’ gồm tất cả các cạnh (v,w) ∈ E sao cho v,w ∈ V’. 
2. Biểu diễn đồ thị 
2.1. Biểu diễn đồ thị bằng ma trận kề 
 Ta dùng một mảng hai chiều, chẳng hạn mảng A, kiểu boolean để biểu diễn 
các đỉnh kề. Nếu đồ thị có n đỉnh thì ta dùng mảng A có kích thước nxn. Giả sử 
các đỉnh được đánh số 1..n thì A[i,j] = true, nếu có cung nối giữa đỉnh thứ i và 
đỉnh thứ j, ngược lại thì A[i,j] = false. Rõ ràng, nếu G là đồ thị vô hướng thì ma 
trận kề sẽ là ma trận đối xứng. 
 Ví dụ 11: Ma trận liền kề với thứ tự các đỉnh v1, v2, v3, v4 là: 
 V1 V2 
 1 1 1 0 
 0 1 0 1 
 V3 V4 
 0 1 1 0 
 0 0 0 1 
 Do ma trận lưu trữ kế tiếp, nên việc truy cập đến các phần tử của ma trận 
kề được thực hiện trực tiếp, với tốc độ nhanh, nhưng cách lưu trữ này rỏ rang là 
tốn không gian nhớ khi n lớn 
2.2. Biểu diễn đồ thị bằng danh sách các đỉnh kề: 
 Trong cách biểu diễn này, ta sẽ lưu trữ các đỉnh kề với một đỉnh i trong một 
danh sách liên kết theo một thứ tự nào đó, gọi là danh sách kề. Mỗi nút trong 
danh sách có qui cách: 
 INFO LINK 
 Trường INFO chứa số j ứng với đỉnh j là kề của i(1<=i<=n) trong danh 
sách lân cận của i 
 Giáo trình Cấu trúc dữ liệu và giải thuật Trang 88 / 92 
 Trường LINK chứa con trỏ, trỏ tới nút tiếp theo trong danh sách. 
 Danh sách có m nút, nếu đỉnh i có m đỉnh kề . 
 Mỗi danh sách như vậy lại có “nút đầu danh sách”. Thường các “nút đầu 
danh sách” là các phần tử của một vec tơ V, có kích thước bằng n, phần tử V[i] 
của V (1<=i<=n), ứng với danh sách kề của nút thứ i, nó chứa địa chỉ của nút 
đầu tiên của danh sách kề này. 
 Ví dụ 11: Hình ảnh danh sách kề biểu diễn đồ thị sau là: 
 V1 V2 
 V3 V4 
V[1] 2 3 
V[2] 1 3 4 
V[3] 1 2 4 
V[4] 2 3 
3. Bài toán tìm đường đi trên đồ thị 
 Trong đời sống, chúng ta thường gặp những tình huống như sau: để đi từ 
địa điểm A đến địa điểm B trong thành phố, có nhiều đường đi, nhiều cách đi; 
có lúc ta chọn đường đi ngắn nhất (theo nghĩa cự ly), có lúc lại cần chọn đường 
đi nhanh nhất (theo nghĩa thời gian) và có lúc phải cân nhắc để chọn đường đi rẻ 
tiền nhất (theo nghĩa chi phí), v.v... 
 Có thể coi sơ đồ của đường đi từ A đến B trong thành phố là một đồ thị, 
với đỉnh là các giao lộ (A và B coi như giao lộ), cạnh là đoạn đường nối hai giao 
lộ. Trên mỗi cạnh của đồ thị này, ta gán một số dương, ứng với chiều dài của 
đoạn đường, thời gian đi đoạn đường hoặc cước phí vận chuyển trên đoạn đường 
đó, ... 
 Giáo trình Cấu trúc dữ liệu và giải thuật Trang 89 / 92 
 Đồ thị có trọng số là đồ thị G=(V,E) mà mỗi cạnh (hoặc cung) e E được 
gán bởi một số thực m(e), gọi là trọng số của cạnh (hoặc cung) e. 
 Cho đơn đồ thị liên thông, có trọng số G=(V,E). Tìm khoảng cách d(u0,v) 
từ một đỉnh u0 cho trước đến một đỉnh v bất kỳ của G và tìm đường đi ngắn nhất 
từ u0 đến v. 
 Ở đây, chúng ta có thuật toán do E. Dijkstra, nhà toán học người Hà Lan, 
đề xuất năm 1959. Phương pháp của thuật toán Dijkstra là: xác định tuần tự đỉnh 
có khoảng cách đến u0 từ nhỏ đến lớn. 
 Trước tiên, đỉnh có khoảng cách đến a nhỏ nhất chính là a, với d(u0,u0)=0. 
Trong các đỉnh v u0, tìm đỉnh có khoảng cách k1 đến u0 là nhỏ nhất. Đỉnh này 
phải là một trong các đỉnh kề với u0. Giả sử đó là u1. Ta có:d(u0,u1) = k1. 
 Trong các đỉnh v u0 và v u1, tìm đỉnh có khoảng cách k2 đến u0 là nhỏ 
nhất. Đỉnh này phải là một trong các đỉnh kề với u0 hoặc với u1. Giả sử đó là u2. 
Ta có: 
 + d(u0,u2) = k2. 
 Tiếp tục như trên, cho đến bao giờ tìm được khoảng cách từ u0 đến mọi 
đỉnh v của G. Nếu V={u0, u1, ..., un} thì: 
 + 0 = d(u0,u0) < d(u0,u1) < d(u0,u2) < ... < d(u0,un). 
 + 
 Thuật toánDijkstra 
 procedureDijkstra (G=(V,E) là đơn đồ thị liên thông, có trọng số với trọng 
số dương) 
 {G có các đỉnh a=u0, u1, ..., un=z và trọng số m(ui,uj), với m(ui,uj) = nếu 
(ui,uj) không là một cạnh trong G} 
 + for i := 1 to n 
 + L(ui) := 
 + L(a) := 0 
 + S := V \ {a} 
 + u := a 
 + while S  
 + begin 
 + for tất cả các đỉnh v thuộc S 
 + if L(u) +m(u,v) < L(v) then L(v) := L(u)+m(u,v) 
 + u := đỉnh thuộc S có nhãn L(u) nhỏ nhất 
 Giáo trình Cấu trúc dữ liệu và giải thuật Trang 90 / 92 
 + {L(u): độ dài đường đi ngắn nhất từ a đến 
 u} 
 + S := S \ {u} 
 + End; 
 Ví dụ 1: Tìm khoảng cách d(a,v) từ a đến mọi đỉnh v và tìm đường đi ngắn 
nhất từ a đến v cho trong đồ thị G sau. 
 + 
 4 6 
 b c d 
 + 
 1 1 2 2 
 + 2 2 
 3 4 3 
 + a e g h 3 
 + 
 2 3 5 5 1 
 + 3 
 n m k 
 + 6 3 
 Giáo trình Cấu trúc dữ liệu và giải thuật Trang 91 / 92 
 + L+ L+ L+ L+ L+ L+ L+ L+ L+ L
 (a) (b) (c) (d) (e) (g) (h) (k) (m) (n) 
 + + + + + + + + + + 
 +0 
 + + + + + + + + + + 
 − 1 3 3 2 
 + 
 +− + − + 5 + + 2 + + + + + 
 3 2 
 + 
 − 
 +− + + 5 + + 2 + + + + 3 − 
 + 
 − − 
 +− + + 4 + + + 6 + + + 3 + − 
 + 
 − − 4 − 6 6 − − 
 + + + + + + + + + + 
 + 
 − − − 10 − 6 6 − − 
 + + + + + + + + + + 
 +− − − 8 − − 9 6 − − 
 + + + + + + + + + + 
 +− − − 8 − − 7 − − − 
 + + + + + + + + + + 
 +− − − 8 − − − − − − 
 + + + + + + + + + + 
 + 
Bài tập thực hành của học viên 
 7.1.Hãy nêu vài ví dụ thực tế biểu diễn được bằng cấu trúc đồ thị. 
 7.2. Cây có phải là một đồ thị ? 
 7.3.Một đồ thị vô hướng có 5 đỉnh thì có tối đa bao nhiêu cung giữa một 
đỉnh với một đồ thị đỉnh khác. 
 7.4. Với đồ thị có n đỉnh thì sao ? 
 7.5. Vẽ một đồ thị định hướng có 5 đỉnh A,B,C,D,E và các cung định 
hướng : (A,B);(C,D);(D,A);(B,D);(B,E);(E,D). 
 7.6.Cho các đồ thị G1 và G2 sau đây : 
Giáo trình Cấu trúc dữ liệu và giải thuật Trang 92 / 92 
 1 2 
 1 2 
 3 
 5 4 
 4 3 
 G1 G2 
Hãy lập ma trận kề của G1 và G2 
Hãy lập danh sách kề của G1 và G2 
YÊU CẦU VỀ ĐÁNH GIÁ KẾT QUẢ HỌC TẬP: 
 Kết quả Kết qủa 
 Tiêu chí đánh giá Hệ số 
 thực hiện học tập 
 Kiến thức 0,3 
 Kỹ năng 0,5 
 Thái độ 0,2 
 Cộng: 
 Giáo trình Cấu trúc dữ liệu và giải thuật Trang 93 / 92 
 TÀI LIỆU THAM KHẢO 
1. Aho, Hopcroft & Ullman, Data Structures and Algorithms,Addison 
 Wesley, 2001. 
2. Robert Sedewick, Algorithms in Java Third Edition,Addison Wesley, 2002. 
 Niklaus Wirth, Data Structures and Algorithms,Prentice Hall, 2004. 
 Robert Sedewick, Algorithms,Addison Wesley, 1983. 
3. Bruno R. Preiss, Data Structures and Algorithms with Object-Oriented 
 Design, Jon Wiley &Sons, 1998. 
4. Đinh Mạnh Tường, Cấu trúc dữ liệu và thuật toán, NXB Đại học Quốc gia 
 Hà Nội. 
5. PGS.TS.Đỗ Xuân Lôi – Cấu trúc dữ liệu và giải thuật – NXB Khoa học và 
 Kỹ thuật – 1997. 
6. PGS.TS.Đỗ Xuân Lôi – Giáo trình Cấu trúc dữ liệu và giải thuật – Vụ giáo 
 dục chuyên nghiệp, NXB Giáo dục - 2002 
7. Trần Hạnh Nhi, Giáo trình cấu trúc dữ liệu,Trường đại học Khoa hoc 
 tựnhiên, tp. Hồ Chí Minh, 2003 
8. PGS. TS. Hoàng Nghĩa Tý, Cấu Trúc Dữ Liệu Và Thuật Toán, Xây Dựng, 
 2002 
9. Gia Việt(Biên dịch), ESAKOV.J , WEISS T, Bài Tập Nâng Cao Cấu 
 Trúc Dữ Liệu Cài Đặt Bằng C, Nhà xuất bản: Thống kê 
10. Minh Trung(Biên dịch), TS. Khuất Hữu Thanh(Biên dịch), Chu Trọng 
 Lương(Tác giả), 455 Bài Tập Cấu Trúc Dữ Liệu - Ứng Dụng Và Cài Đặt 
 Bằng C++,Thống kê . 
11. Robert Sedgewick, Trần Đan Thư(Biên dịch), Bùi thị Ngọc Nga(Biên 
 dịch), Cẩm Nang Thuật Toán (Tập1,2); Khoa học và kỹ thuật 
12. GS. TSKH. Hoàng Kiếm, Giải Một Bài Toán Trên Máy Tính Như Thế 
 Nào,Giáo dục, 2005. 
13. Nguyễn Quốc Lượng, Hoàng Đức Hải – Cấu trúc dữ liệu + giải thuật = 
 chương trình – NXB Giáo dục – 1996.