Lập trình mô phỏng đỉnh và đường của đồ thị

(Post 09/03/2011) Bài toán tìm đường đi hay tìm đường đi ngắn nhất thường có nhiều giải thuật khác nhau. Bài viết sẽ thể hiện cụ thể các ý tưởng tìm đường theo thuật giải của Dijsktra bằng qui trình điển hình để xây dựng ứng dụng đơn giản cho việc tìm đường đi ngắn nhất trong 1 đồ thị vô hướng (cung miêu tả đường 2 chiều) gồm 8 nút.

Để viết chương trình mô phỏng việc tìm đường đi ngắn nhất giữa 2 nút bất kỳ trong 1 đồ thị cho trước, bạn cần thực hiện một số công việc sau:

– Tìm hiểu và nắm vững cách thức hiển thị các dữ liệu lên cửa sổ đồ họa của ứng dụng trên Windows. Các dữ liệu cần hiển thị của 1 ứng dụng chỉ thuộc 1 trong 3 loại: chuỗi văn bản, ảnh bitmap, hình toán học như đoạn thẳng, chữ nhật, vòng tròn… Qui trình hiển thị chuỗi văn bản gồm 3 bước chính: tạo font chữ cần dùng, đăng ký font cho Windows dùng, gọi hàm TextOut() để xuất chuỗi ra cửa sổ. Qui trình hiển thị ảnh bitmap gồm 2 bước chính: nạp ảnh từ file vào bộ nhớ (đối tượng BITMAP), gọi hàm BitBlt() để copy 1 phần hay toàn bộ ảnh gốc và dán vào vùng hiển thị của cửa sổ. Qui trình hiển thị các hình toán học gồm 3 bước chính : tạo đối tượng Pen miêu tả nét vẽ và màu vẽ đường viền, tạo đối tượng Brush miêu tả mẫu tô và màu tô phần diện tích bên trong hình cần vẽ, gọi hàm vẽ để vẽ hình cần vẽ (hàm Lineto để vẽ đoạn thằng, hàm Rectangle để vẽ khối chữ nhật, hàm Ellipse để vẽ khối tròn hay ellipse…).

– Đặc tả đồ thị chứa các nút: đặc tả thuộc tính từng nút và đặc tả các cung nối giữa các nút. Để đặc tả từng nút của đồ thị, bạn sẽ định nghĩa 1 kiểu record gồm nhiều field theo yêu cầu, thí dụ như sau:

//kiểu đặc tả mỗi nút
typedef struct {
//các thuộc tính miêu tả sự hiển thị nút
char* name;//tên nhận dạng nút
int x,y; //tọa độ hiển thị nút
//các thuộc tính phục vụ giải thuật tìm đường
int predecessor;// chỉ số nút đi trước
int length;// độ dài từ nút gốc đến nút này
int label;// trạng thái xử lý nút
} T_Node;

Đăng ký ngay

Đăng ký ngay

– Để đặc tả các cung nối giữa các nút, bạn có thể dùng 1 dãy 2 chiều, phần tử (i,j) trong dãy miêu tả độ dài cung nối từ nút i đến j (=0 nghĩa là không có cung nối).

– Viết hàm tìm đường đi từ nút s đến e theo thuật giải tìm đường nào đó, thí dụ thuật giải của Dijsktra.

Để thấy rõ ràng và cụ thể các ý tưởng nêu trên, chúng tôi giới thiệu qui trình điển hình để xây dựng ứng dụng đơn giản demo việc tìm đường đi ngắn nhất trong 1 đồ thị vô hướng (cung miêu tả đường 2 chiều) gồm 8 nút như sau:

1. Chạy VC++ (hoặc bằng icon shortcut trên desktop hoặc bằng menu Start.Programs…). Tạo Project quản lý ứng dụng bằng cách chọn menu File.New…, khi cửa sổ New hiển thị, chọn loại project “MFC AppWizard (exe)”, chọn vị trí thư mục chứa project, nhập tên Project (thí dụ Timduong) rồi ấn button OK

2. Trong cửa sổ Wizard – Step 1, chọn checkbox “Dialog Based”, rồi ấn button Finish để hoàn thành việc đặc tả các thông số miêu tả Project

3. Khi cửa sổ thiết kế Form ứng dụng hiển thị, chọn từng đối tượng giao diện được tạo sẵn rồi xóa chúng để chuẩn bị thiết kế giao diện theo yêu cầu riêng của mình

4. Vẽ 2 label, 2 combobox, 1 button cần dùng vào cửa sổ ứng dụng như sau:

5. Ấn phải chuột vào button và chọn option Properties để hiển thị cửa sổ thuộc tính cho button, thay đổi thuộc tính Caption = “Bat dau tim”, thuộc tính ID = IDC_START. Tương tự thay đổi thuộc tính ID của combox bên trái là IDC_SLIST, ID của button bên phải là IDC_ELIST

6. Lưu ý việc vẽ 2 comboBox gồm 2 bước: bước đầu vẽ comboBox ở trạng thái chưa được người dùng chọn, sau đó dời chuột tới đầu mũi tên chỉ xuống, ấn chuột vào nó, handle ở giữa dưới được tô đậm, 7 handle còn lại rỗng ruột. Dời chuột về handle tô đậm ruột, kéo chuột đi xuống để xác định kích thước menu pop-up của comboBox khi người dùng chọn nó

7. Chọn menu View.Classwizard để hiển thị cửa sổ Classwizard, chọn tag “Member Variables”, chọn mục IDC_SLIST, ấn button “Add variable” để hiển thị cửa sổ tạo tên biến kết hợp với combobox tương ứng, đặt tên cho tên biến là m_lstart, category là Control. Tương tự đặt tên biến kết hợp với combobox IDC_ELIST là m_lend, category là Control. Ấn chuột vào button OK để đóng cửa sổ Classwizard lại

8. Ấn kép chuột vào button để tạo hàm xử lý sự kiện nhấn chuột cho nó rồi viết code cho hàm này như sau:

void CTimduongDlg::OnStart() {

//xác định chỉ số nút bắt đầu s
int s = m_lstart.GetCurSel();
//xác định chỉ số nút cuối e
int e = m_lend.GetCurSel();
//tìm đường ngắn nhất từ s tới e
len = shortest_path(s,e,path);
//xóa vùng vẽ để hàm OnPaint vẽ lại kết quả
RECT rect;
rect.left = 0; rect.top = 0; rect.right = 800; rect.bottom = 600;
InvalidateRect(&rect);
}

9. Duyệt tìm hàm OnPaint() rồi hiệu chỉnh thân của hàm này thành:

void CTimduongDlg::OnPaint() {
CPaintDC dc(this); // device context for painting
if (IsIconic()) {
SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);
// Center icon in client rectangle
int cxIcon = GetSystemMetrics(SM_CXICON);
int cyIcon = GetSystemMetrics(SM_CYICON);
CRect rect;
GetClientRect(&rect);
int x = (rect.Width() – cxIcon + 1) / 2;
int y = (rect.Height() – cyIcon + 1) / 2;
// Draw the icon
dc.DrawIcon(x, y, m_hIcon);
} else {
//phần viết mới bắt đầu từ đây
//gọi cha làm trước
CDialog::OnPaint();
//định nghĩa các biến cần dùng
int i,j;
HPEN hpen, hpenOld;
HBRUSH hbrush, hbrushOld;
//tạo pen nét liền, 1 pixel màu xanh để vẽ đường viền
hpen = CreatePen(PS_SOLID, 1, RGB(0, 0, 255));
//tạo Brush màu đỏ để tô toàn bộ nền đối tượng
hbrush = CreateSolidBrush(RGB(255, 0, 0));
//đăng ký cho Windows dùng
hpenOld = (HPEN)dc.SelectObject(hpen);
hbrushOld = (HBRUSH)dc.SelectObject(hbrush);
//thiết lập các thuộc tính font để hiển thị chuỗi
LOGFONT strFont;
char bufout[256];
HFONT hFont,hFontOld;
strFont.lfEscapement = 0;
strFont.lfOrientation = 0;
strFont.lfWeight = FW_REGULAR;
strFont.lfItalic =0;
strFont.lfUnderline = 0;
strFont.lfStrikeOut = 0;
strFont.lfCharSet = ANSI_CHARSET;
strFont.lfOutPrecision = OUT_DEFAULT_PRECIS;
strFont.lfClipPrecision = CLIP_DEFAULT_PRECIS;
strFont.lfQuality = PROOF_QUALITY;
strFont.lfPitchAndFamily = VARIABLE_PITCH | FF_ROMAN;
strcpy(strFont.lfFaceName,”Times New Roman”);
strFont.lfHeight = 20;
strFont.lfWidth = 8;
//tạo đối tượng font để hiển thị chuỗi
hFont = CreateFontIndirect(&strFont);
//đăng ký font cho Windows dùng
hFontOld = (HFONT)dc.SelectObject((HFONT)hFont);
//thiết lập các chế độ hiển thị chuỗi
dc.SetBkMode(TRANSPARENT);
dc.SetTextAlign(TA_CENTER);

//vẽ các nút của đồ thị
dc.SetTextColor(RGB(0,0,0));
for (i= 0; i <sonut;>//vẽ khối tròn miêu tả nút i
dc.Ellipse(Node[i].x-4,Node[i].y-4,Node[i].x+4,Node[i].y+4);
//xác định tọa độ hiển thị tên nút
int x = Node[i].x – 20, y = Node[i].y-10;
//hiển thị tên nút
dc.TextOut(x,y,Node[i].name,strlen(Node[i].name));
}</sonut;>

//vẽ các cung nối các nút
dc.SetTextColor(RGB(0,0,255));
for (i=0; i < Sonut; i++)
for (j=i+1; j<sonut;> if (dist[i][j] !=0) { //nếu có cung nối i tới j
int x, y;
//vẽ cung nối từ i tới j
dc.MoveTo (Node[i].x,Node[i].y);
dc.LineTo (Node[j].x,Node[j].y);
//xác định tọa độ hiển thị độ dài cung
x = (Node[i].x + Node[j].x)/2;
y = (Node[i].y + Node[j].y)/2;
//đổi độ dài cung từ số sang chuỗi
sprintf(bufout,”%d”,dist[i][j]);
//vẽ độ dài cung từ i tới j
dc.TextOut(x,y,bufout,strlen(bufout));
}
//khôi phục lại font cũ
dc.SelectObject(hFontOld);
DeleteObject(hFont);
//tạo pen vẽ đường đi tìm được
hpen = CreatePen(PS_SOLID,2, RGB(255, 0,20));
//đăng ký pen cho Windows dùng
hpenOld = (HPEN)dc.SelectObject(hpen);
for (i= 0; i <len-1;>//vẽ từng đoạn của đường đi
dc.MoveTo (Node[path[i]].x,Node[path[i]].y);
dc.LineTo (Node[path[i+1]].x,Node[path[i+1]].y);
}
}
}</len-1;></sonut;>

10. Duyệt tìm hàm OnInitDialog() rồi thêm vào cuối hàm (ngay trước lệnh return TRUE;) đoạn code khởi động như sau:

// TODO: Add extra initialization here
Sonut = 8;
int i,j;
InitGraph(Sonut);
//thiết lập các thuộc tính hiển thị từng nút của đồ thị
Node[0].x = 40; Node[0].y = 140; Node[0].name = “A”;
Node[1].x = 120; Node[1].y = 60; Node[1].name = “B”;
Node[2].x = 360; Node[2].y = 60; Node[2].name = “C”;
Node[3].x = 440; Node[3].y = 140; Node[3].name = “D”;
Node[4].x = 200; Node[4].y = 140; Node[4].name = “E”;
Node[5].x = 280; Node[5].y = 140; Node[5].name = “F”;
Node[6].x = 120; Node[6].y = 220; Node[6].name = “G”;
Node[7].x = 360; Node[7].y = 220; Node[7].name = “H”;
//thiết lập các cung giữa các nút
for (i=0; i < 8; i++)
for (j=i; j<8; j++)
dist[i][j] = 0;
dist[0][1] = 2; dist[0][6] = 6;
dist[1][2] = 7; dist[1][4] = 2;
dist[2][3] = 3; dist[2][5] = 3;
dist[3][7] = 2;
dist[4][6] = 1; dist[4][5] = 2;
dist[5][7] = 2;
dist[6][7] = 4;
//copy ma trận chéo trên sang ma trận chéo dưới
for (i=0; i < 8; i++)
for (j=0; j<i;> dist[i][j] = dist[j][i];
//thiết lập danh sách tên nút cho 2 comboBox
for (i = 0; i < 8 ; i++) {
m_lstart.AddString(Node[i].name);
m_lend.AddString(Node[i].name);
}
return TRUE;</i;>

11. Dời về đầu file, ngay trước lệnh đặc tả class CAboutDlg, viết đoạn code định nghĩa kiểu, biến và hàm tìm đường đi ngắn nhất như sau:

#define INFINITY 1000000 //miêu tả độ dài cung lớn nhất
#define E_Chuathu 0
#define E_Dathu 1
//kiểu đặc tả mỗi nút
typedef struct {
//các thuộc tính miêu tả sự hiển thị nút
char* name;
int x,y;
//các thuộc tính phục vụ giải thuật tìm đường
int predecessor; // chỉ số node đi trước
int length; // độ dài từ nút gốc đến nút này
int label; // trạng thái xử lý nút
} T_Node;

int Sonut; //số nút của đồ thị
int **dist; //dist[i][j] là khoảng cách từ i đến j
int *path; //danh sách các chỉ số nút liên tiếp miêu tả đường đi
int len = 0; //số nút trong đường đi tìm được
T_Node* Node;//thông tin về các nút

//hàm xin cấp phát vùng nhớ cho các dữ liệu đồ thị
void InitGraph(int n) {
int i;
//xin cấp phát vùng nhớ chứa ma trận khoảng cách
dist = (int**) malloc(n*sizeof(int*));
for (i = 0; i <n;>dist[i] = (int*) malloc(n*sizeof(int));
//xin cấp phát vùng nhớ chứa thông tin của các nút
Node = (T_Node*) malloc(n*sizeof(T_Node));
//xin cấp phát vùng nhớ chứa kết quả đường đi tìm được
path = (int*) malloc(n*sizeof(int));
}</n;>

//hàm tìm đường đi ngắn nhất theo thuật giải Dijsktra
int shortest_path(int s, int e, int path[]) {
int i,k,min;
T_Node *p;
//khởi tạo trạng thái đầu của các nút
for (i = 0; i <sonut;>Node[i].predecessor = -1;
Node[i].length= INFINITY;
Node[i].label= E_Chuathu;
}</sonut;>

Node[s].length =0; Node[s].label = E_Dathu; k = s;
do { //từ nút k có đường đi tốt hơn?
for (i =0; i<sonut;> if (dist[k][i] !=0 && Node[i].label == E_Chuathu)
if (Node[k].length +dist[k][i] < Node[i].length) {
Node[i].predecessor = k;
Node[i].length = Node[k].length + dist[k][i];
}
//tìm nút có nhãn E_Chuathu và độ dài nhỏ nhất
k = 0; min = INFINITY;
for (i = 0; i <sonut;>if (Node[i].label == E_Chuathu && Node[i].length < min) {
min = Node[i].length;
k = i;
}
Node[k].label = E_Dathu;
} while (k !=e);
//copy các nút của đường đi tìm được vào biến path
i = 0; k = e;
do {
path [i++] = k ;
k = Node[k].predecessor;
} while (k>=0);
return i;
}//kết thúc hàm shortest_path</sonut;></sonut;>

12. Chọn menu Build.Execute Timduong.exe để dịch và chạy ứng dụng. Nếu bạn thực hiện đúng mọi bước trên thì chương trình không có lỗi và sẽ chạy tốt. Bạn thử chọn 1 nút bắt đầu, 1 nút kết thúc, ấn button “Bat dau tìm”, chương trình sẽ tìm đường đi ngắn nhất giữa 2 nút và hiển thị đường đi lên đồ thị cho bạn thấy trực quan. Bạn hãy thử tìm lần lượt nhiều đường đi theo ý muốn và kiểm tra kết quả xem có đúng không. Cửa sổ ứng dụng sẽ có dạng sau:

Nguyễn Văn Hiệp
(nguồn PC World)

FPT Aptech – Hệ Thống Đào Tạo Lập Trình Viên Quốc Tế