Giải thuật và lập trình - C: II. Kiểu dữ liệu trừu tượng đồ thị

Các phép toán được định nghĩa trên đồ thị là rất đơn giản như là:

• Đọc nhãn của đỉnh.
• Đọc nhãn của cạnh.
• Thêm một đỉnh vào đồ thị.
• Thêm một cạnh vào đồ thị.
• Xoá một đỉnh.
• Xoá một cạnh.
• Lần theo (navigate) các cung trên đồ thị để đi từ đỉnh này sang đỉnh khác.

Thông thường trong các giải thuật trên đồ thị, ta thường phải thực hiện một thao tác nào đó với tất cả các đỉnh kề của một đỉnh, tức là một đoạn giải thuật có dạng sau: For (mỗi đỉnh w kề với v) {thao tác nào đó trên w}.

Để cài đặt các giải thuật như vậy ta cần bổ sung thêm khái niệm về chỉ số của các đỉnh kề với v. Hơn nữa ta cần định nghĩa thêm các phép toán sau đây:

• FIRST(v) trả về chỉ số của đỉnh đầu tiên kề với v. Nếu không có đỉnh nào kề với v thì null được trả về. Giá trị null được chọn tuỳ theo cấu trúc dữ liệu cài đặt đồ thị.
• NEXT(v,i) trả về chỉ số của đỉnh nằm sau đỉnh có chỉ số i và kề với v. Nếu không có đỉnh nào kề với v theo sau đỉnh có chỉ số i thì null được trả về.
• VERTEX(i) trả về đỉnh có chỉ số i. Có thể xem VERTEX(v,i) như là một hàm để định vị đỉnh thứ i để thức hiện một thao tác nào đó trên đỉnh này.