Suy nghĩ và phân tích bài tập thuật giải buổi 1

THUẬT GIẢI

 Đồ thị - buổi 1

Suy nghĩ và phân tích bài tập thuật giải buổi 1

Đề bài tập buổi 1: Viết khai báo cấu trúc, thủ tục xuất nhập trên đồ thị trong các trường hợp sau:

1/ Biểu diễn đồ thị bằng danh sách kề

2/ Biểu diễn đồ thị bằng ma trận kề

3/ Biểu diễn đồ thị có trọng số bằng danh sách kề

4/ Biểu diễn đồ thị có trọng số bằng ma trận kề

5/ Biểu diễn đồ thị vô hướng bằng ma trận kề

1/Tổ chức bằng danh sách kề

Khai báo cấu trúc:

- 1 đồ thị bao gồm:

+       1 danh sách đặc, mỗi phần tử là phần tử đầu tiên của 1 danh sách liên kết đơn. 1 phần tử trong danh sách liên kết gồm 2 thông tin (đỉnh kề và địa chỉ phần tử kế tiếp).

+       Số đỉnh (cũng tức là kích thước của danh sách đặc phía trên).

Thủ tục nhập:

- Trước tiên, về hình thức thủ tục nhập có 2 cách để hiện thực: nhập từ bàn phím và nhập từ tập tin. Điểm khác biệt rõ nhất chính là cửa sổ chú ý. 1 bên có thể là cửa sổ console, 1 bên có thể là cửa sổ notepad. Hãy cùng phân tích ưu và nhược của 2 cách nhập trên. Nếu lập trình thủ tục nhập từ bàn phím thì khi gọi thủ tục người lập trình có thể xuất kèm theo các câu hướng dẫn, các lệnh rẽ nhánh để hướng dẫn người dùng nhập đúng chỗ. Mặt khác, nhập từ tập tin lại khó có thể làm được điều đó, chắc chắn người dùng sẽ phải đọc kĩ cách sử dụng để có thể đưa dữ liệu vào đúng thứ tự, vị trí trong tập tin, nhưng bù lại độ chính xác, tốc độ nhập nhanh hơn tuyệt đối, tiết kiệm thời gian rất nhiều, nhất là khi kiểm thử.

- Tiếp theo đến nội dung nhập, các đỉnh trong đồ thị thường được đánh số tự nhiên bắt đầu từ số 1. Rất nhiều mã giả, tài liệu đều nhất trí đỉnh đồ thị bắt đầu từ số 1. Người dùng khi nhập cũng sẽ nhập đỉnh đồ thị bắt đầu từ số 1. Nếu chúng ta hiện thực bằng ngôn ngữ lập trình C++ thì cũng sẽ có 1 trong 2 lựa chọn:

+       1 là ta lập trình mà bỏ qua phần tử thứ 0 trong danh sách đặc, ưu điểm là nó sẽ khớp với mã giả, dẫn đến hiện thực dễ và nhanh, ít sai. Thống nhất dữ liệu xuất nhập phía người dùng và dữ liệu trong chương trình. Ta chỉ chịu hao phí phần tử thứ 0 đó.

+       2 là mình chịu khó viết lệch mã giả, phần tử thứ 0 đại diện đỉnh số 1, viết thêm các lệnh xử lý xuất nhập, để khi ở phía người dùng: đồ thị bắt đầu bằng đỉnh số 1 và trong lập trình đồ thị bắt đầu bằng đỉnh số 0. Việc này không chỉ đơn thuần là -1 khi nhập và +1 khi xuất mà còn ảnh hưởng đến việc chọn cách quy ước giá trị các trường hợp (thấy rõ hơn trong ma trận kề).

- Sau khi định rõ, thủ tục nhập sẽ được viết theo trình tự sau:

+       Khởi tạo rỗng cho các danh sách liên kết.

+       Đọc dữ liệu, đầu tiên phải là số lượng đỉnh trong đồ thị.

+       Đọc các tập cạnh kề của các đỉnh, kết hợp đưa vào danh sách liên kết các đỉnh tương ứng bằng thủ tục thêm 1 phần tử vào danh sách liên kết (thêm đầu cho dễ, mặc dù thứ tự sẽ bị ngược).

 Thủ tục xuất:

- Hình thức và nội dung tương tự như thủ tục nhập.

- Đơn giản là duyệt từng danh sách liên kết và cho xuất các đỉnh kề.

2/Tổ chức bằng ma trận kề

Khai báo cấu trúc:

- 1 đồ thị bao gồm:

+       1 ma trận.

+       Số đỉnh (cũng tức là kích thước của danh sách đặc phía trên).

Thủ tục nhập và xuất:

- Hình thức và nội dung tương tự như đối với danh sách kề.

- Ta có thể không cần đến hàm khởi tạo. Việc còn lại chỉ là viết xuất nhập ma trận.

•                 Ví dụ các hình thức xuất nhập đối với đồ thị:

Ma trận kề:

<số đỉnh>

<ma trận>

4

0 0 1 1

1 0 0 0

0 1 0 1

0 0 0 0

-----------------------

Danh sách kề:

<số đỉnh>

<số đỉnh kề với đỉnh 1><tập các đỉnh kề đó>

<số đỉnh kề với đỉnh 2><tập các đỉnh kề đó>

….

4

2 3 4

1 1

2 2 4

0

------------------------

Danh sách cạnh:

<số đỉnh>

<số cạnh>

<cạnh thứ 1>

<cạnh thứ 2>

…

4

5

1 3

1 4

2 1

3 2

3 4

------------------------

Còn tiếp…