Chuong 5 ĐỒ THỊ Trong chương này ta sẽ trình bày khái niệm đồ thị. Đó là khái niệm tổng quát nhất trong những cấu trúc dữ liệu mà ta mô tả trong giáo trình này. Các cấu trúc tuyến tính, cấu trúc phân cấp và cả tập hợp mà ta đã học trong những chương trước, đều có thể xem như những trường hợp riêng của đồ thị. Cấu trúc đề thị không chỉ được nghiên cứu và ứng dụng trong Toán học, Tin học mà còn trong nhiều lĩnh vực khoa học công nghệ khác.
Một đồ thị có thể xem là một cấu trúc dữ liệu mà mỗi thành phần dữ liệu của nó có thể có quan hệ với một số tuỳ ý các thành phần đữ liệu trong cấu trúc dó. Tức là, mỗi thành phần đữ liệu trong cấu trúc đồ thị có thể có nhiều phần tử “đứng trước” nó, và có nhiều phần tử “đứng sau” nó. Đồ thị và một số khái niệm cơ bản 5. Khái niệm đồ thị Có hai loại dé thi, dé thị có hướng và đồ thị vô hướng.
Đồ thị có hướng (directed graph hay digraph) G 1A mét cap (V. E), trong dé V 1A mét tap hop hữu hạn các phần tử, mỗi phần tử của nó dược gọi là một đỉnh (vertex), còn E là tập tập các cung (arc) có hướng, mỗi cung nối hai đỉnh của đổ thí một cách có thứ tự, tức là có phân biệt đỉnh đầu và dỉnh cuối. Đỉnh cũng còn được gọi là nút (node), cung có hướng cũng còn được gọi là cạnh có hướng (directed edge). Tap Ð các cung có thể đặt tương ứng với một tập con của tích Đề-các VxV, mỗi phần tử của nó là một cặp đỉnh có thứ tự (v, w) và được biểu thị hình họe bằng một mũi tên có đầu ở w và đuôi ở v.
Người ta hay gọi cung nối hai đỉnh v và w là cung (v, w). Đặc biệU, v và w có thể trùng nhau, khi đó ta có cung (v, v).a thể hiện một đổ thị có hướng với bốn đỉnh và sáu cung. Đồ thị uô hướng là đồ thị mà trong đó mỗi cạnh (edge) JA mét cung néi hai đỉnh không kể đến thứ tự của hai đỉnh đó. Nói cách khác, nếu (v.
w) là cạnh của một đồ thị vô hướng thì (w, v) = (v, w).b thể hiện một đồ thị vô hướng với bốn đỉnh và sấu cạnh. Khi nói để thị mà không chỉ rõ có hướng hay vô hướng sẽ được hiểu là cả hai loại đề thị. Đồ thị có hướng và đồ thị vô hướng 5. Một số khái niệm cơ bản khác Đồ thị con của dé thi G = (V, E) là G'= (V, E’), trong d6 Vcr V, Pc E và G' làm thành một đồ thị (tức là E V'xV9, Đường đi (path) từ đỉnh v đến dỉnh w trong dé thi 1A day đỉnh vụ, v„,., v„ sao cho đỉnh đầu tiên của dãy vị chính là v, đỉnh cuối cùng của dãy chính là w, và giữa mỗi cặp đỉnh liên tiếp, theo đúng thứ tự của dãy đều có một cung (cạnh), nghĩa là (vị, v;), (v;, vạ),.
Đường đi này được gợi là đi qua các đỉnh vị, vạ,. Độ dài của đường đi được tính bằng số cung trên đường đi, trong trường hợp này là n~-1. Một đỉnh v được xem là một đường đi đặc biệt có độ dài bằng 0 từ v đến v. Đường đi đơn là đường đi không tự cắt.
Nói cách khác, đường đi đơn là đường di không chứa cặp đỉnh nào trùng nhau ngoại trừ hai đỉnh đầu và cuối của nó. Chu frinh là đường đi có đúng một cặp đỉnh trùng nhau là đỉnh đầu và đỉnh cuối của đường đi đó, Một đề thị dược gọi là liên thông (connected) néu véi hai dinh bat kì của nó luôn có một đường đi từ đỉnh này tới đỉnh kia. Mỗi dé thị con liên thông tối đại của một đồ thị được gợi là một thành phần liên thông của đỗ thị đó. Đồ thị vô hướng với hai thành phần liên thông 196 Một đồ thị vô hướng liên thông, không chứa chu trình sẽ được gọi là một cây tự do (free tree).2 chỉ ra ví dụ về một đồ thị vô hướng gồm hai thành phần liên thông mà mỗi thành phần liên thông là một cây tự do.
Thuật ngữ cây tự do hàm ý rằng nếu ta xác định một đỉnh bất kì của nó làm gốc thì ta sẽ có một cây thông thường như đã trình bày ở chương trước. Đồ thị có trọng số Trong nhiều trường hợp, người ta gán cho mỗi cạnh của đồ thị một, gia tri ma ta goi 1A chi phi (cost) hay giá của cạnh. Khái niệm này xuất hiện khi nghiên cứu các bài toán thực tế. Chang han, bài toán tim đường đi ngắn nhất giữa mỗi cặp thành phố trong một vùng, hay bài toán phải xây dựng mạng lưới giao thông giữa các thành phố trong một quốc gia sao cho tổng chỉ phí là nhỏ nhất.
Khi đó độ dài của một đường đi không được tính bằng số cạnh trên đường đi đó mà được tính bằng tổng chi phí của các cạnh trên đường đi. Chú ý rằng ta nói về “độ dài” của đường đi ngay cả khi chi phí là một đại lượng khác, như thời gian chẳng hạn. Kiểu dữ liệu trừu tượng đồ thị Ta sẽ trình bày một số thao tác cơ bản trên đề thị. Những thao tác cơ bản đó có thể cài đặt dưới dạng hàm hay thủ tục như trong bảng sau.
Trong những tình huống cụ thể, chẳng hạn với đồ thị vô hướng hay với đồ thị không có trọng số, cần có những thay đổi phù hợp. Thủ tục CREATE(G) Tạo một đồ thị rỗng G. Thủ tục INSERTNODE(G, v) Bổ sung một đỉnh mới v, V = VLÿ {v} Thủ tục INSERTEDGE(G, u, v, w) Bổ sung thêm một cung mới (u, v) có trọng số w vào đổ thị G. Thi tuc DELETENODE(G, v) Xoá đỉnh v và các cạnh liên quan đến nó ra khỏi đồ thị Thủ tục DELETEEDGE(G, u, v) Xoá cạnh (u, v) khỏi đồ thị.
Hàm FIRST (v) Trả ra chỉ số của đỉnh kể đầu tiên của v, Hàm NEXT (y, i} Trả ra chỉ số của đỉnh kể (sau đỉnh có chỉ số i) của v. Hàm VERTEX (v, i) Trả ra đỉnh với chỉ số ¡ trong các đỉnh kể của v. 197 Ví dụ: Để có đỗ thị như trong hình sau, ta sẽ thực hiện các thao tác tương ứng: CREATE(G); INSERTNODEG, 1); INSERTNODE(, 2); INSERTEDGEG, 1, 2); INSERTNODE(GG, 3); INSERTEDGEG, 1, 3); INSERTEDGE(G, 38, 2); INSERTNODE(G, 4); INSERTEDGE(G, 2, 4); INSERTEDGE(, 4, 2); INSERTEDGE(G, 3, 4); Ví dụ: Cần duyệt (đi qua) toàn bộ các đỉnh kể với đỉnh i, tai mỗi đỉnh đó làm một số thao tác: 1 ;= FIRST(v); while i<> NullVertex đo beginw:= VERTEX(v,i); (* Một số thao tác trên w *) i:= NEXT(v,i) end; Hinh 5. Lap trén caéc dinh ké vdiv 5.
Biểu diễn đồ thị - Có nhiều cách để biểu diễn đổ thị trong máy tính, chẳng hạn biểu diễn mối quan hệ đỉnh-canh hay biểu diễn mối quan hệ đỉnh-dỉnh. Trong việc cài đặt một đồ thị, người ta thường lựa chọn mối quan hệ dỉnh-dỉnh mà cụ thể là quan hệ kể cận hay láng giềng giữa các đỉnh. Sau dây, ta sẽ trình bày hai cấu trúc dữ liệu biểu điễn mối quan hệ này. Đó là ma trận các đỉnh kể và danh sách các đỉnh kể, 198 5.
Ma trận các đỉnh kề Một trong các phương pháp thông dụng biểu diễn đề thị là sử dụng ma tran ké (adjacency matrix). Gia st (V, E) 1A mét dé thi. Ma trận kể biểu diễn G là ma trận vuông A cỡ n x n gồm các giá trị hai trạng thai (0-1 hay true-false) được xác định như sau: lnếu(v,w)eE néu(vw)eE „. nấu G là đồ thị không có trọng số.
Aly, wis! 0 néu(v,w)¢E Đối với đồ thị G có trọng số ta đặt Atssd| r nếur là g giá của cung g (v, (V, w w) œ_ nếu không tổn tại cung (v, w) Ví dụ: Bốn đồ thị sau 2) @}——@) lần lượt tương ứng với ma trận: 0110 02 2ø 0 110 0220 0001 œ 0 œ 3 1011 20 4 3 0101 œ4 03 11-01 240 3 0000 œ oo 0 0110 0330 (a) (b) () (d) Để thị có hướng Đổ thị có hướng, có Dé thị vô hướng Đồ thị vô hướng, có trọng số trọng số Hình 5. Ma trận kể Ta có thể cài đặt một số hàm như sau: Type AdjType = arrayv[1.n] of boolean; Vertex = integer; var a: AdjType; function FIRST(v: vertex): vertex ; 199 var u: vertex; begin u:= 1; while (u<=n) and not Af v,u] do u:= utl; FIRST := u mod (n + 1) end; function NEXT (v,i: vertex): vertex; var u: vertex; begin u:= i + 1 ; while (u<=n) and not A[v,u]} do u:= utl; NEXT := u mod (n + 1) end; Hinh 5. Cài đặt một số hàm trên đồ thị vô hướng bằng ma trận kế 5. Biểu diễn đồ thị bằng danh sách các đỉnh kể Phương pháp thứ hai biểu diễn đồ thị là sử dụng danh sách các đỉnh kề ) (2) Header Bon = Hình 5.
Danh sách liên kết các đỉnh kề` Ta xem mỗi đồ thị như một mảng các dang sách. Danh sách thứ ¡ bao gém các nút kể với nút ¡, với ¡ = 1, 2,. Ta có thể cài đặt một số hàm như sau: var Header = arraVy[1.n] o£ LIST; function FIRST (v: vertex): vertex ; begin FIRST:= RETRIEVE (FIRST (Header{ v] ) ) end; function NEXT(v, i: vertex): vertex; var p: POSITION; begin p:= LOCATE(i, Header{ v]) ; NEXT:= RETRIEVE (FIRST (Header v] )) end; Hình 5.7, Cai đặt một số hàm trên đồ thị bằng danh sách liên kết các dinh ké 200 5. Duyệt đồ thị Cũng như đã thực hiện đối với cây, trong mục này chúng ta xét bài toán đi qua các đỉnh của một đồ thị (còn gọi là duyệt hay tìm kiếm).
Ta sẽ trình bày trong mục này hai thuật toán duyệt đồ thị: ưu tiên độ sâu (depth — first) vA uu tién bé réng (breath —first). Tìm kiêm ưu tiên độ sâu (Depth First Searching) Duyệt theo chiều sâu là đi qua tất cả các đỉnh trên một đường đi nào đó của đồ thị cho đến khi không thể đi tiếp được nữa hoặc đường đi tạo thành một chu trình (có đỉnh bị duyệt lại). Việc duyệt được thực hiện tiếp theo bằng cách quay lại đỉnh ngay phía trước và đi theo một đường đi khác nếu thấy xuất hiện. Cứ như vậy, cho đến khi các đỉnh của dé thị được đi qua hết.
Về cấu trúc đữ liệu, để tiện cho việc trình bày, trong các thuật toán duyệt đổ thị dưới đây, ta sử dụng mảng order để ghi thứ tự các đỉnh đã được duyệt, với những đỉnh ¡ chưa được duyệt, ta quy ước order[1] = 0.