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


Đăng ký nhận thông báo về những video mới nhất

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.

Nếu bạn có điều thắc mắc, bạn hãy comment cho V1Study để được giải đáp.
Bài viết này được chia sẻ bởi LongDT. Nếu bạn muốn chia sẻ bài viết, bạn hãy Đăng ký làm thành viên!
« Prev
Next »
Copied !!!