SKKN Phát triển năng lực học sinh thông qua thuật toán tìm kiếm theo chiều sâu (DFS) và tìm kiếm theo chiều rộng (BFS)

n do 
 for j := 1 to n do read(f, a[i, j]); 
 close(f); 
end; 
procedure Init; 
var i: integer; 
begin 
 for i := 1 to n do cx[i]:= true; 
 cx[s]:= false; 
 Truoc[s]:= -1; 
29 
end; 
procedure DFS(u: integer); 
var v: integer; 
begin 
 for v:= 1 to n do 
 if a[u, v] = 1 then 
 if cx[v] = true then 
 begin 
 cx[v]:= false; 
 Truoc[v]:= u; 
 DFS(v); 
 end; 
end; 
procedure TruyVet(v: integer); 
begin 
 if Truoc[v] = -1 then write(f, v) 
 else 
 begin 
 TruyVet(Truoc[v]); 
 write(f, ' -> ', v); 
 end; 
end; 
procedure InKQ; 
begin 
 assign(f, fo); rewrite(f); 
 if cx[t] = true then writeln(f, 'Khong co duong di tu ', s, ' toi ', t) 
 else TruyVet(t); 
 close(f); 
end; 
BEGIN 
 Nhap; 
 Init; 
 DFS(s); 
 InKQ; 
END. 
30 
+) Ngôn ngữ C++ 
#include 
using namespace std; 
const fi = "DOTHI.INP"; 
const fo = "DOTHI.OUT"; 
const int MAXN = 10000; 
string f; 
int n, s, t; 
int a[MAXN][MAXN]; 
bool cx[MAXN]; 
int Truoc[MAXN]; 
void Nhap() 
{ 
 int i,j; 
 freopen(fi,"r",stdin); 
 freopen(fo,"w",stdout); 
 cin >> f >> n >> s >> t; 
 for (i=1; i<=n; i++) 
 for (j=1; j<=n; j++) 
 cin>> f >> a[i][j]; 
} 
void Init() 
{ 
 int i; 
 for (i=1; i<=n; i++) cx[i] = true; 
 cx[s] = false; 
 Truoc[s] = -1; 
} 
void DFS(int u) 
{ 
 int v; 
 for (v=1; v<=n; v++) 
 if (a[u][v] == 1) 
 if (cx[v] == true) 
 { 
 cx[v] = false; 
 Truoc[v] = u; 
 DFS(v); 
 } 
} 
31 
void TruyVet(int v) 
{ 
 if (Truoc[v] == -1) f << v; 
 else 
 { 
 TruyVet(Truoc[v]); 
 f " << v; 
 } 
} 
void InKQ() 
{ 
 f.open(fo, ios::out); 
 if (cx[t] == true) f << "Khong co duong di tu " << s << " toi " << t << endl; 
 else TruyVet(t); 
 f.close(); 
} 
int main() 
{ 
 Nhap(); 
 Init(); 
 DFS(s); 
 InKQ(); 
} 
32 
MỘT SỐ BÀI TẬP ÁP DỤNG 
 Có rất nhiều bài toán vận dụng thuật toán tìm kiếm trên đồ thị và thuật toán 
tìm số vùng liên thông để giải mà chương trình ngắn gọn, hiệu quả. Đặc biệt là các 
bài toán liên quan đến duyệt, tìm kiếm mà cách lưu trữ dữ liệu được đưa về dưới 
dạng ma trận kề (mảng 2 chiều). Dưới đây tôi xin trích ra một số ví dụ để minh họa 
cho điều này: 
Bài tập 5: Đồng cỏ 
Bessie dự định cả ngày sẽ nhai cỏ xuân và ngắm nhìn cảnh xuân trên cánh 
đồng của nông dân John, cánh đồng này được chia thành các ô vuông nhỏ với R (1 
<= R <= 100) hàng và C (1 <= C <= 100) cột. Bessie ước gì có thể đếm được số 
khóm cỏ trên cánh đồng. 
Mỗi khóm cỏ trên bản đồ được đánh dấu bằng một ký tự „#„ hoặc là 2 ký tự 
„#‟ nằm kề nhau (trên đường chéo thì không phải). Cho bản đồ của cánh đồng, hãy 
nói cho Bessie biết có bao nhiêu khóm cỏ trên cánh đồng. 
Ví dụ như cánh đồng dưới dây với R = 5 và C = 6: 
#.... 
..#... 
..#..# 
...##. 
.#... 
Cánh đồng này có 5 khóm cỏ: một khóm ở hàng đầu tiên, một khóm tạo bởi 
hàng thứ 2 và thứ 3 ở cột thứ 2, một khóm là 1 ký tự nằm riêng rẽ ở hàng 3, một 
khóm tạo bởi cột thứ 4 và thứ 5 ở hàng 4, và một khóm cuối cùng ở hàng 5. 
Dữ liệu: dòng 1: 2 số nguyên cách nhau bởi dấu cách: R và C 
Dòng 2..R+1: Dòng i+1 mô tả hàng i của cánh đồng với C ký tự, các ký tự là „#‟ 
hoặc „.‟ . 
Kết quả dòng 1: Một số nguyên cho biết số lượng khóm cỏ trên cánh đồng. 
Ví dụ 
.#.... 
..#... 
..#..# 
...##. 
.#.... 
33 
Kết quả: 5 
Gợi ý làm bài: ở đây ta áp dụng bài tập cơ bản số 3, chính là tìm thành phần 
liên thông, mỗi thành phần liên thông chính là một khóm cỏ. 
+) Ngôn ngữ Pascal 
program VBGRASS; 
const fi=''; 
 nmax=101; 
 cld:array[1..4] of shortint=(0,0,-1,1); 
 clc:array[1..4] of shortint=(-1,1,0,0); 
type matran=array[0..nmax,0..nmax] of char; 
var m,n:byte; 
 a:matran; 
 f:text; 
 visit:array[1..nmax,1..nmax] of boolean; 
 s:word; 
procedure docfile; 
var i,j:byte; 
begin 
 assign(f,fi); 
 reset(f); 
 readln(f,m,n); 
 for i:=1 to m do 
 begin 
 for j:=1 to n do 
 read(f,a[i,j]); 
 if eoln(f) then 
 readln(f); 
 end; 
 close(f); 
end; 
procedure DFS(u,v:byte); 
var i:byte; 
 u1,v1:shortint; 
begin 
 visit[u,v]:=true; 
 for i:=1 to 4 do 
 begin 
 u1:=u+cld[i]; 
 v1:=v+clc[i]; 
 if (a[u1,v1]='#') 
 and (not visit[u1,v1]) then 
 DFS(u1,v1); 
 end; 
34 
end; 
procedure init; 
begin 
 fillchar(visit,sizeof(visit),false); 
 s:=0; 
end; 
procedure xuli; 
var i,j:byte; 
begin 
 init; 
 for i:=1 to m do 
 for j:=1 to n do 
 if (a[i,j]='#') and (not visit[i,j]) then 
 begin 
 DFS(i,j); 
 inc(s); 
 end; 
 writeln(s); 
end; 
begin 
 docfile; 
 xuli; 
end. 
+) Ngôn ngữ C++ 
#include 
#define ll long long 
#define nmax 101 
#define name "VBGRASS" 
using namespace std; 
ll cld[5]={0,0,-1,1},clc[5]={-1,1,0,0}; 
char a[nmax][nmax]; 
ll m,n,s; 
bool visit[nmax][nmax]; 
void docfile() 
{ 
 ll i,j; 
 freopen(name".INP","r",stdin); 
 freopen(name".OUT","w",stdout); 
 cin>>m>>n; 
 for (i=1;i<=m;i++) 
 for (j=1;j<=n;j++) 
 cin>>a[i][j]; 
} 
35 
void init() 
{ 
 memset(visit,false,sizeof(visit)); 
 s=0; 
} 
void DFS(int u,int v) 
{ 
 int u1,v1; 
 visit[u][v]=true; 
 for(int i=0; i<4; i++) // code c++ thi phai la 0 den 3 
 { 
 u1=u+cld[i]; 
 v1=v+clc[i]; 
 if(a[u1][v1]=='#'&& !visit[u1][v1]) DFS(u1,v1); 
 } 
} 
int main() 
{ 
 init(); 
 for(int i=1; i<=m; i++) 
 for(int j=1; j<=n; j++) 
 if(a[i][j]=='#' && !visit[i][j]) 
 { 
 DFS(i,j); 
 s++; 
 } 
 cout<<s; 
} 
Trong các ví dụ dưới đây, tôi chỉ đưa ra cách giải từng ví dụ mà không đưa 
chương trình kèm theo vì đưa vào làm cho đề tài quá dài 
Bài tập 6: Truyền tin 
Một lớp gồm N học viên, mỗi học viên cho biết những bạn mà học viên đó 
có thể liên lạc được (chú ý liên lạc này là liên lạc một chiều, ví dụ : Bạn An có thể 
gửi tin tới Bạn Vinh nhưng Bạn Vinh thì chưa chắc đã có thể gửi tin tới Bạn An). 
Thầy chủ nhiệm đang có một thông tin rất quan trọng cần thông báo tới tất cả các 
học viên của lớp (tin này phải được truyền trực tiếp). Để tiết kiệm thời gian, thầy 
chỉ nhắn tin tới 1 số học viên rồi sau đó nhờ các học viên này nhắn lại cho tất cả 
các bạn mà các học viên đó có thể liên lạc được, và cứ lần lượt như thế làm sao cho 
tất cả các học viên trong lớp đều nhận được tin . 
36 
Câu hỏi : có phương án nào giúp thầy chủ nhiệm với một số ít nhất các học viên 
mà thầy chủ nhiệm cần nhắn? 
Gợi ý làm bài: 
 Có thể nhận thấy bài toán này chính là bài toán 1 đã phát biểu phía trên. Có 
thể coi mỗi học sinh là một đỉnh của đồ thị. Hai học sinh có thể liên lạc được với 
nhau là một cạnh. Từ đó suy ra bài toán này là . Bài toán tìm thành phần liên thông 
của đồ thị. 
Bài tập 7: XÂY KÈ (Đề thi học sinh giỏi tỉnh Nghệ an năm học 2007 – 2008) 
 Một bản đồ hình chữ nhật mô tả một số diện tích hồ nước thiên nhiên được 
chia lưới ô vuông sao cho mỗi ô của lưới chỉ được xem như có 2 trạng thái: hoặc là 
diện tích hồ, hoặc không phải. Người ta muốn xây kè đá xung quanh các hồ này. 
Mỗi cạnh của lưới được xây kè nếu nó là cạnh chung của 2 ô khác trạng thái (các 
cạnh thuộc biên bản đồ không được tính). Lập trình tính tổng chiều dài của kè 
(theo đơn vị cạnh ô lưới). 
Dữ liệu : Vào từ file văn bản KE.INP gồm: 
Dòng đầu ghi M (số dòng của lưới) và N (số cột của lưới). 
Mỗi dòng trong số M dòng tiếp mô tả trạng thái của N ô lưới tương ứng của 
dòng gồm N số 0 (là đất) hoặc 1 (là hồ) theo đúng thứ tự các ô trong lưới. 
Kết quả: Ghi ra file văn bản KE.OUT gồm một số ghi giá trị chiều dài kè. 
Ví dụ: Bản đồ (các ô có mầu xám là diện tích hồ, các cạnh đậm là kè) có các file 
vào, ra tương ứng như sau: 
Giới hạn: M, N không quá 200. 
Gợi ý làm bài: 
KE.INP KE.OUT 
6 11 
0 0 0 1 1 0 0 0 0 0 0 
0 0 1 1 1 1 0 1 0 0 0 
0 0 0 1 0 0 1 1 1 1 0 
0 1 0 0 0 1 1 0 1 1 0 
0 1 1 0 0 0 1 1 1 0 0 
0 0 0 0 0 0 0 1 1 1 1 
43 
37 
- Có thể nhận thấy bài toán này chính là bài toán 1 đã phát biểu phía trên. Có 
thể coi mỗi cạnh của ô vuông là một đỉnh của đồ thị. . Từ đó suy ra bài toán này là 
bài toán đếm các đỉnh của các thành phần liên thông đồ thị. 
Bài tập 8: Đường đi đến số 0 (Đề thi Giáo viên giỏi tỉnh Nghệ an chu kì 2008 – 2011) 
 Mỗi một số nguyên dương đều có thể biểu diễn dưới dạng tích của 2 số 
nguyên dương X,Y sao cho X<=Y. Nếu như trong phân tích này ta thay X bởi X-1 
còn Y bởi Y+1 thì sau khi tính tích của chúng ta thu được hoặc là một số nguyên 
dương mới hoặc là số 0. 
Ví dụ: Số 12 có 3 cách phân tích 1*12,3*4, 2*6 . Cách phân tích thứ nhất cho ta 
tích mới là 0 : (1-1)*(12+1) = 0, cách phân tích thứ hai cho ta tích mới 10 : (3-
1)*(4+1) = 10, còn cách phân tích thứ ba cho ta 7 : (2-1)*(6+1)=7. Nếu như kết 
quả là khác không ta lại lặp lại thủ tục này đối với số thu được. Rõ ràng áp dụng 
liên tiếp thủ tục trên, cuối cùng ta sẽ đến được số 0, không phụ thuộc vào việc ta 
chọn cách phân tích nào để tiếp tục 
Yêu cầu: Cho trước số nguyên dương N (1<=N<=10000), hãy đưa ra tất cả các số 
nguyên dương khác nhau có thể gặp trong việc áp dụng thủ tục đã mô tả đối với N. 
Dữ liệu: Vào từ file Zeropath.Inp chứa số nguyên dương N. 
Kết quả: Ghi ra file văn bản Zeropath.Out : 
 Dòng đầu tiên ghi K là số lượng số tìm được 
 Dòng tiếp theo chứa K số tìm được theo thứ tự tăng dần bắt đầu từ số 0. 
Lưu ý: Có thể có số xuất hiện trên nhiều đường biến đổi khác nhau, nhưng nó chỉ 
được tính một lần trong kết quả. 
Ví dụ: 
ZEROPATH.INP ZEROPATH.OUT 
12 6 
0 3 4 6 7 10 
Gợi ý làm bài: 
Đơn giản là sau mỗi lần phân tích thì chắc chắn kết quả mới luôn nhỏ hơn số 
đó. Vì vậy ta chỉ cần Lưu trữ dưới mảng A: [0..10000] of boolean, trong đó A[i] 
38 
= true nếu nó xuất hiện trên đường đi đó, ngược lại thì A[i] =false. Bằng cách 
loang theo chiều sâu, chúng ta sẽ đánh dấu các số nếu nó được dùng đến, cho đến 
khi không thể nào loang được nữa thì dừng. 
Bài tập 9. Con ngựa 
 Một bàn cờ hình chữ nhật kích thước M x N, M,N nguyên dương không lớn 
hơn 100. Bàn cờ chia thành các ô vuông đơn vị bằng các đường song song với các 
cạnh. Các dòng ô vuông đánh số từ 1 đến M từ trên xuống dưới, các cột đánh số từ 
1 đến N từ trái sang phải. Cho trước một số nguyên dương K<=1000. Một con 
ngựa đứng ở ô [u,v] và nhảy không quá k bước. 
Yêu cầu: Hãy cho biết con ngựa có thể nhảy đến bao nhiêu ô khác ô[u,v] trên bàn 
cờ và đó là những ô nào (khi đứng tại một ô, con ngựa có thể nhảy tới ô đối đỉnh 
của hình chữ nhật kích thước 2 x 3). 
Dữ liệu: Vào từ file MA.INP trong đó : 
Dòng đầu tiên ghi hai số M,N 
Dòng thứ hai ghi số K 
Dòng thứ ba ghi hai số U,V 
Kết quả: Ghi ra file MA.OUT : 
Dòng đầu tiên ghi S là số ô con ngựa có thể nhảy đến 
Tiếp theo là S dòng, mỗi dòng ghi chỉ số dòng và chỉ số cột của một ô mà con ngựa 
có thể nhảy đến. 
MA.INP MA.OUT 
5 5 
1 
2 3 
6 
1 1 1 5 3 1 3 5 4 2 4 4 
Gợi ý làm bài 
Chúng ta sẽ loang theo chiều sâu, tìm kiếm xem những ô nào con mã có thể 
đặt chân đến trong vòng K bước nhảy. 
39 
Bài tập 10: Đường đi trên lưới ô vuông 
 Cho một lưới ô vuông kích thước N x N. Các dòng của lưới được đánh số 
từ 1 đến N từ trên xuống dưới, các cột của lưới được đánh số từ 1 đến N từ trái qua 
phải. Ô nằm trên giao của dòng i, cột j sẽ được gọi là ô (i, j) của lưới. Trên mỗi ô 
(i, j) của lưới người ta ghi một số nguyên dương ai, i, j = 1,2,..., N. Từ một ô bất kỳ 
của lưới được phép di chuyển sang ô có chung cạnh với nó. Thời gian để di chuyển 
từ một ô này sang một ô khác là 1 phút. Cho trước thời gian thực hiện di chuyển là 
K (phút), hãy xác định cách di chuyển bắt đầu từ ô (1, 1) sao cho tổng các số trên 
các ô di chuyển qua là lớn nhất (Mỗi ô của lưới có thể di chuyển qua bao nhiêu lần 
cũng được). 
 Dữ liệu: Vào từ file văn bản NETSUM.INP: 
Dòng đầu tiên chứa các số nguyên dương N, K (2  N 100, 1  K  10000). 
Dòng thứ i trong số N dòng tiếp theo chứa các số nguyên ai1, ai2..., ain, 0 < ai < 
10000 (Các số trên cùng một dòng được ghi cách nhau bởi ít nhất một dấu cách). 
Kết quả: Ghi ra file văn bản NETSUM.OUT: 
Dòng đầu tiên ghi tổng số các số trên đường di chuyển tìm được. 
K dòng tiếp theo mỗi dòng ghi toạ độ của một ô trên đường di chuyển (bắt đầu từ ô 
(1, 1)). Ví dụ: 
NETSUM.INP NETSUM.OUT 
5 7 
1 1 1 1 1 
1 1 3 1 9 
1 1 6 1 1 
1 1 3 1 1 
1 1 1 1 1 
2 1 
1 1 
1 2 
1 3 
2 3 
2 4 
2 3 
2 4 
Gợi ý làm bài: 
Loang các ô có thể đến của các đường đi trên lưới. Tìm cách đi nào có 
đường đi mà tổng lớn nhất thì sẽ lấy. 
40 
Bài tập 11: Miền liên thông. 
Cho bảng chữ nhật chia thành M xN ô vuông đơn vị (M dòng đánh số từ 1 
đến M theo chiều từ trên xuống dưới, N cột đánh số từ 1 đến N theo chiều từ trái 
qua phải. Mỗi ô vuông ghi 1 số 0 hoặc 1. Một miền 0 của bảng là tập hợp các ô 
chung cạnh và chứa số 0). Địa chỉ của một miền là toạ độ [dòng, cột] của ô đầu 
tiên thuộc miền theo thứ tự duyệt từ trái qua phải, từ trên xuống dưới. Hãy tìm số 
miền 0 của bảng và tìm miền 0 có diện tích lớn nhất. 
Dữ liệu vào : File Mien.INP có cấu trúc : 
Dòng đầu ghi 2 số nguyên dương M và N (0<M,N100). 
M dòng tiếp theo thể hiện bảng số theo thứ tự từ trên xuống dưới, mỗi dòng N số 
theo thứ tự từ trái sang phải. 
Dữ liệu ra : File Mien.Out có cấu trúc : 
Dòng thứ nhất ghi số lượng miền 0. 
Dòng thứ 2 ghi diện tích của miền 0 có diện tích lớn nhất. 
Các dòng tiếp theo, mỗi dòng ghi địa chỉ một miền 0 có diện tích lớn nhất. 
 Cách giải : Chúng ta có thể giải theo cách thông thường không vận dụng lý 
thuyết đồ thị. Nhưng rõ ràng, giải theo cách tìm kiếm trên đồ thị sẽ ngắn gọn, hiệu 
quả và nhanh hơn nhiều. Thuật toán thể hiện rõ ràng, dễ hiểu. Cụ thể như sau : 
Thực hiện vòng lặp. 
Tìm một ô chứa số 0 chưa thăm là ô x có toạ độ dòng và cột là (i,j). 
Thực hiện thuật toán BDF (tìm kiếm theo chiều rộng) để tìm được miền 0 chứa ô 
x. Trong quá trình duyệt cũng tính diện tích của miền (mỗi lần đến một ô mới thì 
tăng diện tích lên một đơn vị). 
Mỗi lần thực hiện xong thủ tục BDF thì tìm được một miền 0 chứa ô (i,j), lưu kết 
quả (toạ độ i, j và diện tích của miền vào mảng KQ) đồng thời tăng biến đếm số 
miền 0. 
Hiện số lượng miền 0. 
Duyệt mảng KQ để tìm miền 0 có diện tích lớn nhất. Hiện diện tích miền 0 lớn 
nhất 
41 
Duyệt mảng KQ lần thứ 2 để hiện toạ độ từng ô đại diện cho mỗi miền 0 có diện 
tích bằng diện tích của miền lớn nhất. 
Bài tập 12: Hệ thống đảo cung cấp xăng. 
Vùng Hạ Long có N hòn đảo được đánh số từ 1 đến N. Toạ độ hòn đảo thứ i 
trên mặt phẳng toạ độ được cho bởi cặp số nguyên xi, yi. Trên mỗi đảo có bể chứa 
xăng có khả năng cung cấp đầy các thiết bị chứa xăng của ca nô. Biết rằng các thiết 
bị chứa xăng của ca nô không thể chứa đủ số xăng đi hết M km. Hãy tìm hành trình 
cho ca nô đi từ đảo U đến đảo V (0<U, VN) mà số lần ghé vào các đảo để lấy 
xăng là nhỏ nhất. 
Dữ liệu vào : File văn bản DAO.INP có cấu trúc 
Dòng đầu ghi 4 số nguyên dương N, M, U, V 
Các dòng tiếp theo, dòng thứ i trong các dòng này ghi 2 số nguyên dương xi, yi. 
Kết quả : Ghi ra file văn bản DAO.OUT 
Nếu có đường đi thì dòng đầu tiên ghi số đảo ghé vào lấy xăng (trừ U và V) 
Dòng thứ 2 ghi số hiệu các đảo đó theo thứ tự hành trình. Nếu không có đường đi 
thì ghi „KHONG CO DUONG DI‟ 
Ví dụ : 
DAO.INP DAO.OUT 
12 10 1 12 
0 0 
8 0 
8 6 
0 8 
10 4 
15 4 
20 8 
20 0 
25 8 
25 4 
25 0 
30 4 
4 
2 6 7 9 
42 
Cách giải : Áp dụng thuật toán tìm kiếm theo chiều rộng để được đường đi qua ít 
đảo nhất. Điều kiện để đi được từ đảo A sang đảo B là khoảng cách AB M km. 
Trong quá trình tìm kiếm theo chiều rộng tổ chức thêm mảng Truoc(N) với 
Truoc[i] = j có nghĩa là đảo j ngay trước đảo i trên hành trình đi từ U đến V. 
43 
IV. KẾT QUẢ VÀ KIẾN NGHỊ ĐỀ XUẤT 
1. Kết quả nghiên cứu : 
 Sau nhiều năm áp dụng dạy học sinh khối 11 áp dụng cách làm này tôi 
nhận thấy: 
- Vận dụng kiến thức về lý thuyết đồ thị vào giải các bài toán thì sẽ giúp học 
sinh giải quyết được một số lớp bài toán góp phần nâng cao chất lượng dạy học 
cũng như phát triển được năng lực của học sinh. 
- Tiếp cận chương trình mới môn Tin học 2018 phần đồ thị có trong mạch 
kiến thức CS 
- Trong các năm học 2018 – 2019 tôi đã ứng dụng đề tài nghiên cứu của 
mình đối với một số lớp khối 11 ở trường THPT Lê Viết Thuật và đã tổng hợp số 
liệu về kết quả đạt được của học sinh như sau: 
STT Lớp Sĩ số Giỏi Khá Trung bình 
Không đạt yêu 
cầu 
1 11A1 40 17% 54% 29% 
2 11T1 42 25% 50% 25% 
3 11A4 38 2% 39% 47% 11% 
- Kết quả học sinh giỏi cấp tỉnh các năm gần đây đạt kết quả cao 
- Ứng dụng lý thuyết đồ thị vào dạy học và bồi dưỡng học sinh giỏi Tin học 
tại các trường THPT có ý nghĩa rất quan trọng trong việc nâng cao chất lượng, hiệu 
quả dạy học, qua đó giúp học sinh nhận thức đúng đắn vai trò, vị trí của môn học. 
Hơn nữa việc ứng dụng lý thuyết đồ thị tạo được hứng thú học tập cho học sinh, 
phát huy tính tích cực, chủ động, nhằm phát triển tư duy sáng tạo và năng lực giải 
quyết vấn đề trong thực tiển cuộc sống. Đề tài này đã giúp bản thân tôi tìm hiểu 
sâu hơn kiến thức về lý thuyết đồ thị và giúp học sinh tìm hiểu thêm một luồng 
kiến thức mới để làm phong phú ý tưởng thuật toán của mình, tạo nền tảng cơ bản 
và bàn đạp để tiến xa hơn về con đường lập trình. Xã hội càng phát triển càng đặt 
44 
ra nhiều yêu cầu mới, do đó các bài toán đặt ra hiện nay ngày càng thiên về khuynh 
hướng giải bằng lý thuyết đồ thị. 
- Từ hai thuật toán cơ bản chúng ta chỉ cần thay đổi các tham số hoặc thêm 
vào các tham số khác nhau thì được các bài toán khác nhau qua đó các em hiểu rõ 
hơn về hai thuật toán cơ bản trong đồ thị. 
2. Kiến nghị, đề xuất : 
Sau khi thực hiện đề tài này tôi xin mạnh dạn đưa ra một số đề xuất như sau : 
 - Để học sinh thực sự hiểu rõ trong lập trình về phần đồ thị đối với học sinh lớp 
11 thì cần tăng cường hơn nữa lượng thời gian trong phân phối chương trình để 
học sinh rèn luyện các dạng bài tập. 
 - Giáo viên cần khai thác các bài toán cơ bản từ hai thuật toán cơ bản (DFS và 
BFS) từ đó mở rộng ra các bài toán tương tự khác. 
 - Với đối tượng học sinh khá giỏi thì có thể khai thác sâu hơn một số bài toán 
khó và các mô hình khác trong đồ thị. 
45 
C. KẾT LUẬN 
Với cách làm này thì phát triển được năng lực, kỹ năng lập trình của học 
sinh, từ đó giúp các em hứng thú để tiếp tục tìm hiểu và giải quyết các bài toán 
khác, các thầy, cô có thể áp dụng cách làm này với nhiều dạng bài tập khác nhau 
để thấy được hiệu quả. Tôi hy vọng các thầy cô có thể tạo được niềm đam mê cho 
học sinh và tạo ra những học sinh có tư duy kỹ năng lập trình đó cũng là mong 
muốn của tôi khi viết SKKN này. 
Trên đây là sáng kiến nghiệm của bản thân trong quá trình giảng dạy cũng 
như bồi dưỡng học sinh khá giỏi. Mặc dù đã rất cố gắng nhưng không thể tránh 
khỏi những sai sót, rất mong được sự góp ý kiến, phê bình, phản hồi của các đồng 
nghiệp (ĐT: 0976124889). 
 Tôi xin chân thành cảm ơn! 
 Vinh, ngày 05 tháng 03 năm 2020 
 Người viết 
 Hoàng Xuân Thắng 
46 
TÀI LIỆU THAM KHẢO 
[1] – Hồ Sỹ Đàm, Đỗ Đức Đông, Lê Minh Hoàng, Nguyễn Thanh Tùng – Tài liệu 
chuyên Tin học, quyển 1, quyển 2, NXB Giáo dục, 2011. 
[2]. Một số tài liệu về quy hoạch động của thầy Lê Minh Hoàng 
[3]. Bài tập trên  
https://www.spoj.com/PTIT/problems  
47 
MỤC LỤC 
NỘI DUNG Trang 
Phần A: Phần mở đầu 
1. Lý do chọn đề tài 
2. Mục tiêu nhiện vụ của đề tài 
3. Giả thiết khoa học 
4. Phương pháp nghiên cứu 
1 
1 
1 
2 
2 
Phần B: Nội dung 3 
I. Cơ sở lý luận của vấn đề 
 1. Đồ thị và tầm quan trọng 
 2. Biểu điễn đồ thị 
 3. Tìm kiếm trên đồ thị và tìm thành phần liên thông của đồ thị 
 4. Đường đi ngắn nhất trên đồ thị 
3 
3 
4 
5 
8 
II. Thực trạng của vấn đề 
 1. Thuần lợi 
 2. Khó khăn 
8 
8 
8 
 III. Hai thuật toán và một số bài tập áp dụng 
 1. Tìm kiếm theo chiều rộng 
 2. Tìm kiếm theo chiều sâu 
10 
10 
16 
IV. Kết quả và kiến nghị đề xuất 
 1. Kết quả nghiên cứu 
 2. Kiến nghị đề xuất 
43 
43 
44 
Phần C. Kết luận 45 
Tài liệu tham khảo 46