TỔNG LIÊN ĐỒN LAO ĐỘNG VIỆT NAM
TRƯỜNG ĐẠI HỌC TƠN ĐỨC THẮNG
KHOA CƠNG NGHỆ THƠNG TIN

BÀI TẬP LỚN MƠN TỐN TỔ HỢP VÀ ĐỒ THỊ

Trình bày một số thuật tốn
trong 10 bài lab

THÀNH PHỐ HỒ CHÍ MINH, NĂM 2021


TỔNG LIÊN ĐỒN LAO ĐỘNG VIỆT NAM
TRƯỜNG ĐẠI HỌC TƠN ĐỨC THẮNG
KHOA CƠNG NGHỆ THƠNG TIN

BÀI TẬP LỚN MƠN TỐN TỔ HỢP VÀ ĐỒ THỊ

Trình bày một số thuật tốn
trong 10 bài lab

THÀNH PHỐ HỒ CHÍ MINH, NĂM 2021


1

LỜI CẢM ƠN
Đầu tiên, chúng em xin gửi lời cảm ơn đến giảng viên bộ môn lý thuyết và thực
hành đã giảng dạy, truyền đạt những kiến thức quan trọng giúp chúng em hiểu rõ hơn
về nội dung của môn Tốn tổ hợp và đồ thị.
Trong thời gian tìm hiểu và học tập về bộ môn này, chắc chắn chúng em sẽ cịn

rất nhiều thiếu sót và vẫn chưa thể hiểu rõ được tất cả những kiến thức liên quan đến
mơn học. Do đó, trong q trình thực hiện bài tiểu luận sẽ có những chỗ chưa chính
xác, mong thầy/ cơ bỏ qua cũng như góp ý để chúng em hồn thiện hơn bài tiểu luận
của mình.
Chúng em xin chân thành cảm ơn!


2

ĐỒ ÁN ĐƯỢC HỒN THÀNH
TẠI TRƯỜNG ĐẠI HỌC TƠN ĐỨC THẮNG
Tôi xin cam đoan đây là sản phẩm đồ án của riêng tôi / chúng tôi và được sự
hướng dẫn của GV;. Các nội dung nghiên cứu, kết quả trong đề tài này là trung thực và
chưa công bố dưới bất kỳ hình thức nào trước đây. Những số liệu trong các bảng biểu
phục vụ cho việc phân tích, nhận xét, đánh giá được chính tác giả thu thập từ các
nguồn khác nhau có ghi rõ trong phần tài liệu tham khảo.
Ngồi ra, trong đồ án cịn sử dụng một số nhận xét, đánh giá cũng như số liệu
của các tác giả khác, cơ quan tổ chức khác đều có trích dẫn và chú thích nguồn gốc.
Nếu phát hiện có bất kỳ sự gian lận nào tơi xin hồn tồn chịu trách nhiệm
về nội dung đồ án của mình. Trường đại học Tôn Đức Thắng không liên quan đến
những vi phạm tác quyền, bản quyền do tôi gây ra trong q trình thực hiện (nếu có).
TP. Hồ Chí Minh, ngày 24 tháng 04 năm 2021
Tác giả
(ký tên và ghi rõ họ tên)


3

PHẦN XÁC NHẬN VÀ ĐÁNH GIÁ CỦA GIẢNG VIÊN
Phần xác nhận của GV hướng dẫn


_________________________________________________________
_________________________________________________________
_________________________________________________________
_________________________________________________________
_________________________________________________________
_________________________________________________________
_________________________________________________________
Tp. Hồ Chí Minh, ngày tháng năm
(kí và ghi họ tên)

Phần đánh giá của GV chấm bài

_________________________________________________________
_________________________________________________________
_________________________________________________________
_________________________________________________________
_________________________________________________________
_________________________________________________________
_________________________________________________________
Tp. Hồ Chí Minh, ngày tháng năm
(kí và ghi họ tên)


4

TĨM TẮT
Trình bày lại một số thuật tốn trong 10 bài lab.
+ Phần 1: tổ hợp (lab2 - lab5)
Mỗi lab chọn một thuật tốn để trình bày

Tương ứng với mỗi thuật toán cần nêu cụ thể:
- Giới thiệu bài toán
- Ý tưởng thuật toán
- Các bước thực hiện
- Mã giả
- Mã nguồn
+ Phần 2: đồ thị
Tạo class Graph thực thi các phương thức sau: load (đọc dữ liệu đồ thị từ
file, duyệt theo chiều rộng, duyệt theo chiều sâu, tìm cây khung nhỏ nhất (Prim
+ Kruskal))
Trình bày lớp Graph:
- Các thuộc tính
- Tương ứng với mỗi phương thức trình bày thuật toán sử dụng
- Mã giả
- Mã nguồn
- Hướng dẫn chạy chương trình


1

MỤC LỤC
LỜI CẢM ƠN.................................................................................................................i
PHẦN XÁC NHẬN VÀ ĐÁNH GIÁ CỦA GIẢNG VIÊN..........................................iii
TÓM TẮT..................................................................................................................... iv
MỤC LỤC...................................................................................................................... 1
CHƯƠNG 1 – TỔ HỢP..................................................................................................3
1.1 Thuật toán Mixed radix generation................................................................3
1.1.1 Giới thiệu bài toán...........................................................................3
1.1.2 Ý tưởng thuật toán...........................................................................3
1.1.3 Các bước thực hiện..........................................................................3

1.1.4 Mã giả..............................................................................................3
1.1.5 Mã nguồn.........................................................................................4
1.2 Thuật toán Heap.............................................................................................5
1.2.1 Giới thiệu bài toán...........................................................................5
1.2.2 Ý tưởng thuật toán...........................................................................5
1.2.3 Các bước thực hiện..........................................................................5
1.2.4 Mã giả..............................................................................................6
1.2.5 Mã nguồn.........................................................................................6
1.3 Thuật toán Steinhaus – Johnson – Trotter......................................................7
1.3.1 Giới thiệu bài toán...........................................................................7
1.3.2 Ý tưởng thuật toán...........................................................................7
1.3.3 Các bước thực hiện..........................................................................7
1.3.4 Mã giả..............................................................................................8
1.1.5 Mã nguồn.........................................................................................9
1.4 Lexicographic to generate combinations.......................................................9
1.4.1 Giới thiệu bài toán....................................................................................10
1.4.2 Ý tưởng thuật toán.........................................................................10


2

1.4.3 Các bước thực hiện........................................................................10
1.4.4 Mã giả............................................................................................10
1.4.5 Mã nguồn.......................................................................................10
CHƯƠNG 2 – ĐỒ THỊ.................................................................................................11
2.1 Các thuật toán..............................................................................................11
2.1.1 Duyệt theo chiều sâu......................................................................11
2.1.2 Duyệt theo chiều rộng....................................................................12
2.1.3 Prim - Tìm cây khung nhỏ nhất......................................................14
2.1.4 Kruskal - Tìm cây khung nhỏ nhất.................................................17

2.2 Mã giả..........................................................................................................17
2.2.1 Duyệt theo chiều sâu......................................................................17
2.2.2 Duyệt theo chiều rộng....................................................................18
2.2.3 Prim - Tìm cây khung nhỏ nhất......................................................18
2.2.4 Kruskal - Tìm cây khung nhỏ nhất.................................................19
2.3 Mã nguồn.....................................................................................................19
2.3.1 Duyệt theo chiều sâu......................................................................19
2.3.2 Duyệt theo chiều rộng....................................................................20
2.3.3 Kruskal - Tìm cây khung nhỏ nhất.................................................21


3

CHƯƠNG 1 – TỔ HỢP
1.1 Thuật toán Mixed radix generation
1.1.1 Giới thiệu bài toán
Nếu bạn muốn tạo tất cả (a 1, ..., an), trong đó mỗi aj là một trong các chữ số thập
phân {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Chúng ta có thể sử dụng các vòng lặp lồng nhau khi n
là một số tương đối nhỏ. Tuy nhiên, nếu n là một số lớn thì các vịng lặp lồng nhau
khơng hiệu quả.

1.1.2 Ý tưởng thuật toán
Thuật toán Mixed radix generation truy cập tất cả n bộ giá trị thỏa mãn
0 ≤ aj khi nó xảy ra tràn, trong đó các giới hạn trên m j có thể khác trong các thành phần khác
nhau của vectơ (a1, ..., an).

1.1.3 Các bước thực hiện
Ta chọn một phần tử từ mỗi hàng. ['01', '10', '22', '30', '40'] là một tùy chọn (hoặc
đường dẫn) trong số 3x2x3x1x2 = 36 đường dẫn khả thi.

Một cách hệ thống hơn để trích xuất đường dẫn là sử dụng hệ thống số cơ số
hỗn hợp. Cơ số tương ứng với trên là [3, 2, 3, 1, 2].
Bây giờ, để in tất cả các đường dẫn có thể có, trước tiên chúng ta sử dụng vịng
lặp for để trích xuất độ dài của mỗi hàng và đặt nó thành cơ số của đối tượng
MixedRadix được khởi tạo bằng 0. Vòng lặp qua tất cả các chỉ số đường dẫn có thể
bằng cách tăng giá trị của nó bằng 1 sẽ dẫn đến việc tạo ra tất cả các đường dẫn có thể.
Danh sách các chữ số của số này tương đương với biểu diễn chỉ số của một đường dẫn.
Một đường dẫn có thể được sử dụng để trích xuất tất cả các phần tử của A tương
ứng với đường dẫn đó.

1.1.4 Mã giả
Các biến phụ a0 và m0 được giới thiệu để giúp chúng ta thuận tiện hơn.


4

Bước 1: [Khởi tạo] Đặt aj ← 0 cho 0 ≤ j ≤ n, và đặt m0 ← 2
Bước 2: [Truy cập] Truy cập n-tuple (a1, ..., an). (Chương trình muốn kiểm tra tất
cả n-tuples đang thực hiện nhiệm vụ của nó.)
Bước 3: [Chuẩn bị thêm một cái] Đặt j ← n
Bước 4: [Thực hiện nếu cần] Nếu aj = mj - 1, đặt aj ← 0, j ← j - 1 và lặp lại bước
này.
Bước 5: [Tăng, trừ khi hồn thành] Nếu j = 0, kết thúc thuật tốn. Nếu không,
hãy đặt aj ← aj + 1 và quay lại Bước 2.

1.1.5 Mã nguồn
m1 = [1,3,2]
def M(m1):
n = len(m1)
a = [0] * (n+1)

m = [0] + m1
flag = True
while (flag):
print(a[1:])
j=n
while a[j] == m[j] - 1:
a[j] = 0
j -= 1
if j==0:
flag = False
else:
a[j] += 1
M(m1)

1.2 Thuật toán Heap
1.2.1 Giới thiệu bài toán
Các cách sắp xếp khác nhau của một số lượng nhất định bằng cách lấy một số
hoặc tất cả tại một thời điểm, được gọi là hốn vị. Ví dụ, một cơng ty phải chọn 3 cán
bộ từ nhóm 6 ứng viên. Có bao nhiêu cách khác nhau để thực hiện việc này nếu các


5

ứng viên là khác biệt. Chúng ta đang chọn một bộ ba (s1, s2, s3) với mỗi người là một
ứng cử viên và thứ tự rất quan trọng. Điều này có nghĩa là chúng ta đang tìm một hốn
vị 3 từ một tập hợp 6 phần tử. Vậy có: P(6, 3) = 6! 3! = 6.5.4 = 120 cách khác nhau để
chọn các sĩ quan này.

1.2.2 Ý tưởng thuật toán
Thuật toán của Heap tạo ra tất cả hoán vị của một mảng dữ liệu có độ dài n.

Thuật tốn giảm thiểu chuyển động: nó tạo ra mỗi hốn vị từ cái trước bằng cách hoán
đổi cho nhau một cặp phần tử; n − 2 phần tử cịn lại khơng bị xáo trộn.

1.2.3 Các bước thực hiện
Giả sử cho một tập hợp là {1, 2, 3}. Ta cần tạo ra tất cả hốn vị của n = 3 số đã
cho:

Hình 1. Ví dụ về thuật tốn Heap
Thuật tốn tạo ra (n-1)! hoán vị của n-1 phần tử đầu tiên, liền kề phần tử cuối
cùng với mỗi phần tử này. Điều này sẽ tạo ra tất cả các hoán vị kết thúc bằng phần tử
cuối cùng.
Nếu n lẻ, hoán đổi phần tử đầu tiên và cuối cùng và nếu n chẵn, sau đó hốn đổi
phần tử thứ i (i là bộ đếm bắt đầu từ 0) và phần tử cuối cùng và lặp lại thuật tốn trên
cho đến khi tơi nhỏ hơn n.


6

Trong mỗi lần lặp, thuật toán sẽ tạo ra tất cả các hoán vị kết thúc bằng phần tử
cuối cùng hiện tại.

1.2.4 Mã giả
Input: n: integer, A: an array
if n = 1 then output A
else
for i:=0; i¡ n; i ++ do
If n is even then
Swap(A[i], A[n-1])
else
Swap(A[0], A[n-1])

Output: các tập hợp được hoán vị

1.2.5 Mã nguồn
a = [1,2,3]
n=3
def heapPer(a, n):
if n == 1:
print(a)
return
for i in range(n):
heapPer(a, n-1)
if n%2 == 0:
a[i], a[n-1] = a[n-1], a[i]
else:
a[0], a[n-1] = a[n-1], a[0]
heapPer(a,n)

1.3 Thuật toán Steinhaus – Johnson – Trotter
1.3.1 Giới thiệu bài toán


7

Thuật toán Steinhaus – Johnson – Trotter hay thuật toán Johnson – Trotter, còn
được gọi là các thay đổi đơn giản, là một thuật toán được đặt theo tên của Hugo
Steinhaus, Selmer M. Johnson và Hale F. Trotter tạo ra tất cả các hoán vị của n phần tử.

1.3.2 Ý tưởng thuật toán
Đối với thuật toán Steinhaus – Johnson – Trotter. Mỗi hốn vị trong dãy mà nó
tạo ra khác với hốn vị trước đó bằng cách hốn đổi hai phần tử liền kề của dãy. Thuật

toán này sử dụng một thuật ngữ gọi là số nguyên di động. Một số nguyên được cho là
di động, nếu số liền kề trên hướng của nó nhỏ hơn số này.
Lưu ý:
- Nếu một số nguyên ở cột ngoài cùng bên phải trỏ về bên phải thì số ngun đó
khơng di động.
- Nếu một số nguyên ở cột ngoài cùng bên trái trỏ về bên trái, thì nó khơng di
động.

1.3.3 Các bước thực hiện
Giả sử ta có thuật tốn này với n = 4
← 1 ← 2 ← 3 ← 4 phần tử di động lớn nhất là 4
← 1 ← 2 ← 4 ← 3 đổi 3 và 4; phần tử di động lớn nhất là 4
← 1 ← 4 ← 2 ← 3 đổi 2 và 4; phần tử di động lớn nhất là 4
← 4 ← 1 ← 2 ← 3 đổi 1 và 4; phần tử di động lớn nhất là 3, sau khi bước 4 này
đã đi hết chiều từ phải sang trái, được chèn vào hoán vị ngắn hơn ”123”. Trong bước
tiếp theo "123" được xử lý - để mang lại "132".
4 → ← 1 ← 3 ← 2 hoán đổi 2 và 3; thay đổi hướng của tất cả giá trị lớn hơn 3;
phần tử di động lớn nhất là 4
← 1 4 → ← 3 ← 2 hoán đổi 1 và 4; phần tử di động lớn nhất là 4
← 1 ← 3 4 → ← 2 hoán đổi 3 và 4; phần tử di động lớn nhất là 4
← 1 ← 3 ← 2 4 → hoán đổi 2 và 4; phần tử di động lớn nhất là 3, sau khi bước
4 này đã đi hết từ phải sang trái.


8

Thuật toán sẽ tiến hành hoán vị "4", và mỗi khi 4 đến đầu đối diện "3" sẽ được
chuyển vị. Hoán vị cuối cùng thu được là → 2 → 1 3 ← 4 ←. Lưu ý rằng nó khác với
hoán vị ban đầu chỉ bởi một chuyển vị (2 và 1).
Thuật tốn có tính chất sau: bất kỳ hai hốn vị liên tiếp nào mà nó tạo ra đều

nhận được từ nhau bằng một chuyển vị duy nhất của các phần tử liền kề. Các thuật tốn
có thuộc tính như vậy được gọi là thuật toán "thay đổi tối thiểu"

1.3.4 Mã giả
Input: cho trước k là số nguyên di động hiện tại, p []: dãy đầu vào, pi []: nghịch
đảo của p, d [] là hướng của số nguyên di động.
begin
if k ≤ N then
JohnsonSteinhausTrotter (k+1, p, pi, d)
for c := 1...k-1 loop
x := pi[k];
y := x + d[k];
j := p[y];
p[x] := j; pi[j] := x;
p[y] := k; pi[k] := y;
JohnsonSteinhausTrotter (k+1, p, pi, d)
end loop
d[k] := -d[k]
else
output(p)
end if
end

1.1.5 Mã nguồn
def trotter(k,p[],pi[],d[]):


9

if k <= N:

trotter(k+1,p,pi,d)
for c in range(1,k-1):
x = pi[k]
y = x + d[k]
j = p[y]
p[x] = j
pi[j] = x
p[y] = k
pi[k] = y
trotter(k+1,p,pi,d)
d[k] = -d[k]
else:
return(p)
trotter()

1.4 Lexicographic to generate combinations
1.4.1 Giới thiệu bài tốn
Tốn tổ hợp thường được mơ tả là tổ hợp của n thứ, lấy t tại một thời điểm,
thường được gọi đơn giản là tổ hợp thứ t của n thứ, là một cách để chọn một tập con có
kích thước t từ một tập hợp có kích thước n cho trước. Ví dụ, một cơng ty phải chọn 3
cán bộ từ nhóm 6 ứng cử viên. Có bao nhiêu cách khác nhau có thể được thực hiện nếu
các sĩ quan không khác biệt. Nếu các viên chức không khác nhau, các bộ ba (s1, s2,
s3), (s1, s3, s2), (s3, s2, s1), v.v. là giống nhau vì các vị trí là tương tự. Vì vậy, chúng ta
đang tìm một tổ hợp 3 từ tập hợp 6 số hạng. Vậy có: C (6, 3) = 6! (6−3)! 3! = 6! 3! 3! =
5.4 = 20

1.4.2 Ý tưởng thuật toán
Thuật toán này tạo ra tất cả các kết hợp t ct ... c2c1 trong số n số {0,1, ..., n-1},
sao cho n> t> 0. Các biến bổ sung ct + 1 và ct + 2 được sử dụng như các vệ tinh.

1.4.3 Các bước thực hiện
Đối với bất kỳ tổ hợp r nào, một quy trình để tạo tổ hợp lớn nhất tiếp theo có thể
được phát triển. Một tổ hợp a1a2 ... ar theo thứ tự từ vựng được đưa ra cho một tập hợp


10

{1,2,3, ..., n}. Trong tập hợp {1, 2, 3, 4, 5, 6}, kết hợp 4 có thể là {1, 2, 5, 6}. Để có
được kết hợp lớn nhất tiếp theo, ta tìm a i cuối cùng trong tổ hợp sao cho a i! = N - r + i.
(Phần tử cuối cùng trong tổ hợp với ai! = N - r + i là 2.) Thay ai bằng a i + 1 và aj bằng
aj + j - i + 1, với j = i +1, i + 2 ,. .., r. (Điều này tạo ra kết hợp lớn nhất tiếp theo, {1, 3,
4, 5}.

1.4.4 Mã giả
Bước 1: [Khởi tạo] Đặt cj ← j −1 cho 1 ≤ j ≤ t; tập hợp cj + 1 ← n, cj + 2 ← 0 và j≤t
Bước 2: [Truy cập] Truy cập tổ hợp ct ... c2c1.
Bước 3: [Tìm j] Đặt j ← 1. Sau đó, while c j + 1 = cj + 1, đặt cj ← j - 1 và j ← j +
1; lặp lại cho đến khi cj + 1 6 = cj + 1
Bước 4: [Xong?] Kết thúc thuật toán nếu j> t
Bước 5: [Tăng cj] Đặt cj ← cj + 1 và quay lại bước 2.

1.4.5 Mã nguồn
def comLexicographic(n,k):
if n<=k<0:
print("not satisfy n<=k<0")
return []
c=[]
c=list(range(k))
c.append(n)
c.append(0)

Out=[]
j=0
while jj=0
Out.append(c[:k].copy())
while c[j+1]==c[j]+1:
c[j]=j
j+=1
c[j] = c[j] + 1
return Out
print(comLexicographic(7,4))


11

CHƯƠNG 2 – ĐỒ THỊ
2.1 Các thuật toán
2.1.1 Duyệt theo chiều sâu
Giải thuật tìm kiếm theo chiều sâu (Depth First Search – viết tắt là DFS), còn
được gọi là giải thuật tìm kiếm ưu tiên chiều sâu, là giải thuật duyệt hoặc tìm kiếm trên
một cây hoặc một đồ thị và sử dụng stack (ngăn xếp) để ghi nhớ đỉnh liền kề để bắt đầu
việc tìm kiếm khi khơng gặp được đỉnh liền kề trong bất kỳ vòng lặp nào. Giải thuật
tiếp tục cho tới khi gặp được đỉnh cần tìm hoặc tới một nút khơng có con. Khi đó giải
thuật quay lui về đỉnh vừa mới tìm kiếm ở bước trước.

Trong hình minh họa trên, giải thuật tìm kiếm theo chiều sâu đầu tiên duyệt từ
các đỉnh A tới B tới C tới D sau đó tới E, sau đó tới F và cuối cùng tới G. Giải thuật
này tuân theo qui tắc sau:
Qui tắc 1: Duyệt tiếp tới đỉnh liền kề mà chưa được duyệt. Đánh dấu đỉnh mà đã
được duyệt. Hiển thị đỉnh đó và đẩy vào trong một ngăn xếp (stack).

12

Qui tắc 2: Nếu khơng tìm thấy đỉnh liền kề, thì lấy một đỉnh từ trong ngăn xếp
(thao tác pop up). (Giải thuật sẽ lấy tất cả các đỉnh từ trong ngăn xếp mà khơng có các
đỉnh liền kề nào)
Qui tắc 3: Lặp lại các qui tắc 1 và qui tắc 2 cho tới khi ngăn xếp là trống.

2.1.2 Duyệt theo chiều rộng
Tìm kiếm theo chiều rộng (BFS) là một thuật tốn tìm kiếm trong đồ thị trong
đó việc tìm kiếm chỉ bao gồm 2 thao tác: (a) cho trước một đỉnh của đồ thị; (b) thêm
các đỉnh kề với đỉnh vừa cho vào danh sách có thể hướng tới tiếp theo. Có thể sử dụng
thuật tốn tìm kiếm theo chiều rộng cho hai mục đích: tìm kiếm đường đi từ một đỉnh
gốc cho trước tới một đỉnh đích, và tìm kiếm đường đi từ đỉnh gốc tới tất cả các đỉnh
khác. Trong đồ thị khơng có trọng số, thuật tốn tìm kiếm theo chiều rộng ln tìm ra
đường đi ngắn nhất có thể. Thuật tốn BFS bắt đầu từ đỉnh gốc và lần lượt nhìn các
đỉnh kề với đỉnh gốc. Sau đó, với mỗi đỉnh trong số đó, thuật tốn lại lần lượt nhìn
trước các đỉnh kề với nó mà chưa được quan sát trước đó và lặp lại. Xem thêm thuật
tốn tìm kiếm theo chiều sâu, trong đó cũng sử dụng 2 thao tác trên nhưng có trình tự
quan sát các đỉnh khác với thuật tốn tìm kiếm theo chiều rộng.

Thuật toán sử dụng một cấu trúc dữ liệu hàng đợi để lưu trữ thông tin trung gian
thu được trong quá trình tìm kiếm:
1. Chèn đỉnh gốc vào hàng đợi (đang hướng tới)


13

2. Lấy ra đỉnh đầu tiên trong hàng đợi và quan sát nó

*Nếu đỉnh này chính là đỉnh đích, dừng q trình tìm kiếm và trả về kết quả.
*Nếu khơng phải thì chèn tất cả các đỉnh kề với đỉnh vừa thăm nhưng chưa được quan
sát trước đó vào hàng đợi.
3. Nếu hàng đợi là rỗng, thì tất cả các đỉnh có thể đến được đều đã được quan sát –
dừng việc tìm kiếm và trả về "khơng thấy".
4. Nếu hàng đợi khơng rỗng thì quay về bước 2.

2.1.3 Prim - Tìm cây khung nhỏ nhất
Bài tốn cây khung (cây bao trùm) nhỏ nhất của đồ thị là một trong số những
bài tốn tối ưu trên đồ thị có nhiều ứng dụng khác nhau trong đời sống. Để minh hoạ
thuật tốn, chúng ta tham khảo một vài mơ hình thực tế tiêu biểu của bài toán:
Bài toán xây dựng đường giao thông: giả sử ta muốn xây dựng một hệ thống
đường nối n thành phố sao cho giữa các thành phố bất kì ln có đường đi.Bài tốn đặt
ra là tim cây khung nhỏ nhất trên đồ thị, mỗi thành phố ứng với một đỉnh sao cho tổng
chi phí xây dựng đường đi là nhỏ nhất.
Bài toán nối mạng máy tính: Cần nối mạng một hệ thống gồm n máy tính
đánhsố từ 1 đến n. Biết chi phí nối máy i với máy j là c[i,j], i,j = 1, 2, . . . ,n
( thơngthường chi phí này phụ thuộc vào độ dài cáp nối cần sử dụng). Hãy tìm cách nối
mạng sao cho tổng chi phí nối mạng là nhỏ nhất.
Ý tưởng: nạp dần các đỉnh vào cây khung. Mỗi lần chọn một đỉnh chưa nạp sao
cho đỉnh đó kề và gần nhất với các đỉnh đã nạp.


14

Mơ tả thuật tốn: - Từ đỉnh bắt đầu, lưu đỉnh bắt đầu vào tập các đỉnh đã xét, lưu
độ dài từ đỉnh này đến tất cả các đỉnh khác (nếu có đường đi trực tiếp). Tập đỉnh đã
xét: đỉnh 0

- Chọn đỉnh gần nhất với tập đỉnh đã xét (đỉnh 2), lưu đỉnh này vào tập các đỉnh

đã xét. Cập nhật khoảng cách đến các đỉnh còn lại nếu đỉnh vừa chọn có khoảng cách
nhỏ hơn so với khoảng cách đã lưu trước đó. Tập đỉnh đã xét: đỉnh 0, đỉnh 2


15

- Tiếp tục thực hiện lặp lại bước 2 cho đến khi tìm được cây khung nhỏ nhất.


16

2.1.4 Kruskal - Tìm cây khung nhỏ nhất
Thuật tốn Kruskal là một thuật toán trong lý thuyết đồ thị để tìm cây bao trùm
nhỏ nhất của một đồ thị liên thơng có trọng số. Nói cách khác, nó tìm một tập hợp
các cạnh tạo thành một cây chứa tất cả các đỉnh của đồ thị và có tổng trọng số các cạnh
là nhỏ nhất.Thuật tốn Kruskal là một ví dụ của thuật tốn tham lam.
Thuật tốn Kruskal dựa trên mơ hình xây dựng cây khung nhỏ nhất bằng thuật
tốn hợp nhất.
Thuật tốn khơng xét các cạnh với thứ tự tuỳ ý.
Thuật toán xét các cạnh theo thứ tự đã sắp xếp theo trọng số.


17

Để xây dựng tập n-1 cạnh của cây khung nhỏ nhất - tạm gọi là tập K, Kruskal đề
nghị cách kết nạp lần lượt các cạnh vào tập đó theo nguyên tắc như sau:
Ưu tiên các cạnh có trọng số nhỏ hơn.
Kết nạp cạnh khi nó khơng tạo chu trình với tập cạnh đã kết nạp trước đó.
Đó là một nguyên tắc chính xác và đúng đắn, đảm bảo tập K nếu thu đủ n - 1
cạnh sẽ là cây khung nhỏ nhất.

2.2 Mã giả
2.2.1 Duyệt theo chiều sâu
Step 1: For each vertex v do visited[v] = false
Step 2: S = EmptyStack
Step 3: Push(S,s)
Step 4: while not Empty(S) do
u = Pop(S)
if not visited[u] then
visted[u] = true
for all w in Adj[u] do
if not visited[w] then Push(S,w)
end for
end if
end while

2.2.2 Duyệt theo chiều rộng
Step 1: For each vertex v do visited[v] = false
Step 2: Q = EmptyQueue
Step 3: Enqueue(Q,s)
Step 4: while not Empty(Q) do
u = Dequeue(Q)
if not visited[u] then


18

visted[u] = true
for all w in Adj[u] do
if not visited[w] then Enqueue(Q,w)

end for
end if
end while

2.2.3 Prim - Tìm cây khung nhỏ nhất
Step 1: choose u ∈ V ; V 0 = {u}; E0 = 0
Step 2: for i = 1 : n − 1 do
E00 = edges linking V to V’
choose e = (u, v) ∈ E00 of minimal weight and such that
(V’ ∪ v, E0 e) is acyclic;
V’= V ∪ v; E0 = E0 ∪ e;
end for

2.2.4 Kruskal - Tìm cây khung nhỏ nhất
Step 1: Eord = sort(E); E0 = 0; Erest = Eord
Step 2: while |E0 | > n − 1 do
α = f irst(Erest); Erest = Erest \ α;
if (V, E’ ∪ {α}) is acyclic then
E’ = E’ ∪ {α}
end if
end while

2.3 Mã nguồn
2.3.1 Duyệt theo chiều sâu
def DFS(A):
visited=[[]]
k=0


19

S=list(range(len(A[0])))
S=S[::-1]
while S:
u=S.pop()
if check(visited,u)==-1:
visited[k].append(u)
for i in range(len(A[u])):
if A[u][i]!=0:
w=i
if check(visited,w)==-1:
visited[k].append(w)
if len(S)>0:
visited.append([])
k+=1
else:
continue
visited.pop()
return visited
print("Ex1: ",DFS(A))

2.3.2 Duyệt theo chiều rộng
def BFS(A):
visited=[[]]
k=0
S=list(range(len(A[0])))
while S:
u=S[0]
del(S[0])