Viết hàm list neighbors(graph* g, int x) trả về danh sách các đỉnh kề của x.
Chương 13 – Đồ thò Giáo trình Cấu trúc dữ liệu và Giải thuật 339Chương 13 – ĐỒ THỊ Chương này trình bày về các cấu trúc toán học quan trọng được gọi là đồ thò. Đồ thò thường được ứng dụng trong rất nhiều lónh vực: điều tra xã hội, hóa học, đòa lý, kỹ thuật điện,…. Chúng ta sẽ tìm hiểu các phương pháp biểu điễn đồ thò bằng các cấu trúc dữ liệu và xây dựng một số giải thuật tiêu biểu liên quan đến đồ thò. 13.1. Nền tảng toán học 13.1.1. Các đònh nghóa và ví dụ Một đồ thò (graph) G gồm một tập V chứa các đỉnh của đồ thò, và tập E chứa các cặp đỉnh khác nhau từ V. Các cặp đỉnh này được gọi là các cạnh của G. Nếu e = (ν, µ) là một cạnh có hai đỉnh ν và µ, thì chúng ta gọi ν và µ nằm trên e, và e nối với ν và µ. Nếu các cặp đỉnh không có thứ tự, G được gọi là đồ thò vô hướng (undirected graph), ngược lại, G đượïc gọi là đồ thò có hướng (directed graph). Thông thường đồ thò có hướng được gọi tắt là digraph, còn từ graph thường mang nghóa là đồ thò vô hướng. Cách tự nhiên để vẽ đồ thò là biểu diễn các đỉnh bằng các điểm hoặc vòng tròn, và các cạnh bằng các đường thẳng hoặc các cung nối các đỉnh. Đối với đồ thò có hướng thì các đường thẳng hay các cung cần có mũi tên chỉ hướng. Hình 13.1 minh họa một số ví dụ về đồ thò. Đồ thò thứ nhất trong hình 13.1 có các thành phố là các đỉnh, và các tuyến bay là các cạnh. Trong đồ thò thứ hai, các nguyên tử hydro và carbon là các đỉnh, các liên kết hóa học là các cạnh. Hình thứ ba là một đồ thò có hướng cho biết khả năng truyền nhận dữ liệu trên mạng, các nút của mạng (A, B, …, F) là các đỉnh và các đường nối các nút là có hướng. Đôi khi cách chọn tập đỉnh và tập cạnh cho đồ thò phụ thuộc vào giải thuật mà chúng ta dùng để giải bài toán, chẳng hạn bài toán liên quan đến quy trình công việc, bài toán xếp thời khóa biểu,… Đồ thò được sử dụng để mô hình hóa rất nhiều dạng quá trình cũng như cấu trúc khác nhau. Đồ thò có thể biểu diễn mạng giao thông giữa các thành phố, hoặc các thành phần của một mạch in điện tử và các đường nối giữa chúng, hoặc cấu trúc của một phân tử gồm các nguyên tử và các liên kết hóa học. Những người dân trong một thành phố cũng có thể được biểu diễn bởi các đỉnh của đồ thò mà các cạnh là các mối quan hệ giữa họ. Nhân viên trong một công ty có thể được biểu diễn trong một đồ thò có hướng mà các cạnh có hướng cho biết mối quan hệ của họ với những người quản lý. Những người này cũng có thể có những mối quan hệ “cùng làm việc” biểu diễn bởi các cạnh không hướng trong một đồ thò vô hướng. Chương 13 – Đồ thò Giáo trình Cấu trúc dữ liệu và Giải thuật 340 13.1.2. Đồ thò vô hướng Một vài dạng của đồ thò vô hướng được minh họa trong hình 13.2. Hai đỉnh trong một đồ thò vô hướng được gọi là kề nhau (adjacent) nếu tồn tại một cạnh nối từ đỉnh này đến đỉnh kia. Trong đồ thò vô hướng trong hình 13.2 a, đỉnh 1 và 2 là kề nhau, đỉnh 3 và 4 là kề nhau, nhưng đỉnh 1 và đỉnh 4 không kề nhau. Một đường đi (path) là một dãy các đỉnh khác nhau, trong đó mỗi đỉnh kề với đỉnh kế tiếp. Hình (b) cho thấy một đường đi. Một chu trình (cycle) là một đường đi chứa ít nhất ba đỉnh sao cho đỉnh cuối cùng kề với đỉnh đầu tiên. Hình (c) là một chu trình. Một đồ thò được gọi là liên thông (connected) nếu luôn có một đường đi từ một đỉnh bất kỳ đến một đỉnh bất kỳ nào khác. Hình (a), (b), và (c) là các đồ thò liên thông. Hình (d) không phải là đồ thò liên thông. Nếu một đồ thò là không liên thông, chúng ta xem mỗi tập con lớn nhất các đỉnh liên thông nhau như một thành phần liên thông. Ví dụ, đồ thò không liên thông ở hình (d) có hai thành phần liên thông: một thành phần chứa các đỉnh 1,2 và 4; một thành phần chỉ có đỉnh 3. Hình 13.1 – Các ví dụ về đồ thò Hình 13.2 – Các dạng của đồ thò vô hướng Chương 13 – Đồ thò Giáo trình Cấu trúc dữ liệu và Giải thuật 341Phần (e) là một đồ thò liên thông không có chu trình. Chúng ta có thể nhận thấy đồ thò cuối cùng này thực sự là một cây, và chúng ta dùng đặc tính này để đònh nghóa: Một cây tự do (free tree) được đònh nghóa là một đồ thò vô hướng liên thông không có chu trình. 13.1.3. Đồ thò có hướng Đối với các đồ thò có hướng, chúng ta có thể có những đònh nghóa tương tự. Chúng ta yêu cầu mọi cạnh trong một đường đi hoặc một chu trình đều có cùng hướng, như vậy việc lần theo một đường đi hoặc một chu trình có nghóa là phải di chuyển theo hướng chỉ bởi các mũi tên. Những đường đi (hay chu trình) như vậy được gọi là đường đi có hướng (hay chu trình có hướng). Một đồ thò có hướng được gọi là liên thông mạnh (strongly connected) nếu nó luôn có một đường đi có hướng từ một đỉnh bất kỳ đến một đỉnh bất kỳ nào khác. Trong một đồ thò có hướng không liên thông mạnh, nếu bỏ qua chiều của các cạnh mà chúng ta có được một đồ thò vô hướng liên thông thì đồ thò có hướng ban đầu được gọi là đồ thò liên thông yếu (weakly connected). Hình 13.3 minh họa một chu trình có hướng, một đồ thò có hướng liên thông mạnh và một đồ thò có hướng liên thông yếu. Các đồ thò có hướng trong phần (b) và (c) hình 13.3 có các cặp đỉnh có các cạnh có hướng theo cả hai chiều giữa chúng. Các cạnh có hướng là các cặp có thứ tự và các cặp có thứ tự (ν, µ) và (µ,ν) là khác nhau nếu ν ≠ µ. Trong đồ thò vô hướng, chỉ có thể có nhiều nhất một cạnh nối hai đỉnh khác nhau. Tương tự, do các đỉnh trên một cạnh theo đònh nghóa là phải khác nhau, không thể có một cạnh nối một đỉnh với chính nó. Tuy nhiên, cũng có những trường hợp mở rộng đònh nghóa, người ta cho phép nhiều cạnh nối một cặp đỉnh, và một cạnh nối một đỉnh với chính nó. 13.2. Biểu diễn bằng máy tính Nếu chúng ta chuẩn bò viết chương trình để giải quyết một bài toán có liên quan đến đồ thò, trước hết chúng ta phải tìm cách để biểu diễn cấu trúc toán học của đồ thò như là một dạng nào đó của cấu trúc dữ liệu. Có nhiều phương pháp Hình 13.3–Các ví duï về đồ thò có hướng Chương 13 – Đồ thò Giáo trình Cấu trúc dữ liệu và Giải thuật 342được dùng phổ biến, về cơ bản chúng khác nhau trong việc lựa chọn kiểu dữ liệu trừu tượng để biểu diễn đồ thò, cũng như nhiều cách hiện thực khác nhau cho mỗi kiểu dữ liệu trừu tượng. Nói cách khác, chúng ta bắt đầu từ một đònh nghóa toán học, đó là đồ thò, sau đó chúng ta tìm hiểu cách mô tả nó như một kiểu dữ liệu trừu tượng (tập hợp, bảng, hay danh sách đều có thể dùng được), và cuối cùng chúng ta lựa chọn cách hiện thực cho kiểu dữ liệu trừu tượng mà chúng ta chọn. 13.2.1. Biểu diễn của tập hợp Đồ thò được đònh nghóa bằng một tập hợp, như vậy một cách hết sức tự nhiên là dùng tập hợp để xác đònh cách biểu diễn nó như là dữ liệu. Trước tiên, chúng ta có một tập các đỉnh, và thứ hai, chúng ta có các cạnh như là tập các cặp đỉnh. Thay vì thử biểu diễn tập các cặp đỉnh này một cách trực tiếp, chúng ta chia nó ra thành nhiều phần nhỏ bằng cách xem xét tập các cạnh liên quan đến từng đỉnh riêng rẽ. Nói một cách khác, chúng ta có thể biết được tất cả các cạnh trong đồ thò bằng cách nắm giữ tập Eν các cạnh có chứa ν đối với mỗi đỉnh ν trong đồ thò, hoặc, một cách tương đương, tập Aν gồm tất cả các đỉnh kề với ν. Thật vậy, chúng ta có thể dùng ý tưởng này để đưa ra một đònh nghóa mới tương đương cho đồ thò: Đònh nghóa: Một đồ thò có hướng G bao gồm tập V, gọi là các đỉnh của G, và, đối với mọi ν ∈ V, có một tập con Aν , gọi là tập các đỉnh kề của ν. Từ các tập con Aν chúng ta có thể tái tạo lại các cạnh như là các cặp có thứ tự theo quy tắc sau: cặp (ν, w) là một cạnh nếu và chỉ nếu w∈ Aν. Xử lý cho tập các đỉnh dễ hơn là tập các cạnh. Ngoài ra, đònh nghóa mới này thích hợp với cả đồ thò có hướng và đồ thò vô hướng. Một đồ thò là vô hướng khi nó thỏa tính chất đối xứng sau: w∈ Aν kéo theo ν∈ Aw với mọi ν, w∈V. Tính chất này có thể được phát biểu lại như sau: Một cạnh không có hướng giữa ν và w có thể được xem như hai cạnh có hướng, một từ ν đến w và một từ w đến ν. 13.2.1.1. Hiện thực các tập hợp Có nhiều cách để hiện thực tập các đỉnh trong cấu trúc dữ liệu và giải thuật. Cách thứ nhất là biểu diễn tập các đỉnh như là một danh sách các phần tử của nó, chúng ta sẽ tìm hiểu phương pháp này sau. Cách thứ hai, thường gọi là chuỗi các bit (bit string), lưu một trò Boolean cho mỗi phần tử của tập hợp để chỉ ra rằng nó có hay không có trong tập hợp. Để đơn giản, chúng ta sẽ xem các phần tử có thể có của tập hợp được đánh chỉ số từ 0 đến max_set-1, với max_set là số phần tử tối đa cho phép. Điều này có thể được hiện thực một cách dễ dàng bằng cách sử dụng thư viện chuẩn (Standard Template Library- STL) Chương 13 – Đồ thò Giáo trình Cấu trúc dữ liệu và Giải thuật 343std::bitset |