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

Hướng dẫn code BFS

I/ Cấu trúc dữ liệu:

-       Dùng 1 danh sách kề để biểu diễn 1 đồ thị không trọng số

-       Dùng 1 hàng đợi để duy trì trật tự tìm kiếm theo chiều rộng

-       Dùng 1 mảng màu để không lặp lại các đỉnh tìm kiếm

-       Dùng 1 mảng để xác định đường đi ngắn nhất từ đỉnh nguồn s đến các đỉnh đã được tìm kiếm

-       Dùng 1 mảng để lưu trữ đỉnh đi trước của đỉnh được tìm kiếm

Vậy điều ta cần làm trước tiên là tổ chức và cài đặt : 1 danh sách kề, 1 queue và 3 array.

1/ Danh sách kề

Thành phần: 1 array, mỗi phần tử trong mảng bắt đầu 1 danh sách liên kết,( giống giống bảng băm ).

Thao tác:

-       Danh sách liên kết cần các thao tác: khởi tạo rỗng, thêm 1 phần tử vào danh sách liên kết (nên là thêm cuối), xuất(để kiểm tra).

-       Khởi tạo đồ thị rỗng, nhập đồ thị, xuất đồ thị(để kiểm tra).

2/ Hàng đợi:

Có 2 cách tổ chức là danh sách đặc hoặc danh sách liên kết, cả 2 cách đều có ưu điểm riêng.

-       Danh sách đặc thì cài đặt dễ, truy xuất nhanh.

-       Danh sách liên kết thì vì ta đã cài đặt danh sách liên kết ở danh sách kề phía trên rồi, chỉ thêm 1 số thao tác . Nhưng nếu trước đó ta cài danh sách liên kết gồm 2 con trỏ thành phần (trỏ vào đầu và cuối danh sách) thì sẽ không cần duyệt tuần tự, kết quả là truy xuất nhanh.

Thành phần: danh sách, 2 biến vị trí đầu và cuối danh sách.

Thao tác: khởi tạo rỗng, xét xem rỗng hay không, đưa 1 phần tử vào hàng đợi, lấy 1 phần tử ra hàng đợi.

3/ Mảng màu:

Kiểu của mảng màu phụ thuộc vào kiểu của màu. Kiểu của màu do người lập trình chọn, để đơn giản có thể là kiểu nguyên hay kiểu kí tự. Việc quy ước màu nào là chữ gì số mấy cũng là do người lập trình. Ngoài ra, ta cũng có thể dùng từ khóa define để black, gray, white đại diện cho các số 2, 1, 0 để dễ và tiện trong cài đặt.

4/ Mảng đường đi:

Lưu số cạnh ít nhất từ đỉnh nguồn s đến các đỉnh đã tìm kiếm dĩ nhiên là kiểu số nguyên

5/ Mảng lưu trữ đỉnh đi trước của đỉnh được tìm kiếm có kiểu giống với kiểu của đỉnh đồ thị

Nếu ta tổ chức đỉnh của đồ thị kiểu số nguyên thì mảng lưu trữ đỉnh sẽ kiểu số nguyên

Ví dụ về thành phần cấu trúc:

struct Node{

          int info;

          Node* next;

};

typedef Node* StNode;

struct GRAPH{

          StNode list[SIZE];

          int n;//the number of vertices

};

typedef int DATA;

struct QUEUE

{

          DATA array[SIZE];

          int front;

          int rear;

};

#define white 0

#define gray 1

#define black 2

Cuối cùng ta khai báo:

1 đồ thị G                  GRAPH G;

1 hàng đợi Q              QUEUE Q;

1 mảng color              int color[SIZE];     

1 mảng d                   int d[SIZE]; 

1 mảng pi                  int pi[SIZE];

II/ Thuật giải

Bắt đầu cài đặt dựa vào mã giả.

Đây là mã giả và mã C++ của mình tương ứng. Vì tổ chức còn dở nên chưa sát với mã giả.

Mã giả:                                                              Mã C++:

BFS(G, s)                                               void BFS(GRAPH G,int s)

                                                            {

                                                                   int u,v;

                                                                   StNode p;

 1  for each vertex u thuộc [G] - {s}                  for(int i=0; i<G.n ; i++)

                                                                   {

 2       do color[u] ← WHITE                                       color[i] = white;

 3           d[u] ← ∞                                                   d[i] = -1;

 4          pi[u] ← NIL                                                 pi[i] = -1;

                                                                   }

 5  color[s] ← GRAY                                         color[s] = gray;

 6  d[s] ← 0                                                    d[s] = 0;

 7  pi[s] ← NIL                                                pi[s] = -1;

 8  Q ← Ø                                                      emptyqueue(Q);

 9  ENQUEUE(Q, s)                                          enqueue(Q,s);

10  while Q ≠ Ø                                            while(!isemptyqueue(Q))

                                                                   {

11      do u ← DEQUEUE(Q)                                        dequeue(Q,u);

12         for each v thuộc Adj[u]                                 for(p=G.list[u];p!=NULL;p=p->next)

                                                                             {

                                                                                      v = p->info;

13             do if color[v] = WHITE                                      if(color[v]==white)  

14                   then color[v] ← GRAY                                            color[v] = gray;

15                        d[v] ← d[u] + 1                                                d[v] = d[u]+1;

16                        pi[v] ← u                                                         pi[v] = u;

17                        ENQUEUE(Q, v)                                                enqueue(Q,v);

                                                                             }

18         color[u] ← BLACK                                         color[u] = black;

                                                                   }

                                                            }

Kết quả của BFS chính là 2 mảng pi và d. Trong đó mảng pi sẽ là dữ liệu quan trọng trong ứng dụng BFS cho bài toán tìm đường đi ngắn nhất.

Về hàm main thì cũng sẽ nhập đồ thị à BFS() à xuất pi và d ra để kiểm tra xem đúng chưa. Vậy thôi. :P