LỜI CAM ĐOAN
Tôi xin cam đoan, kết quả luận văn hoàn toàn là kết quả của tự bản thân
tôi tìm hiểu, nghiên cứu dưới sự hướng dẫn của TS. Hồ Cẩm Hà.
Các tài liệu tham khảo được trích dẫn và chú thích đầy đủ.
Học viên
Nguyễn Thị Chinh
Trang 3
LỜI CẢM ƠN
Trước hết, tôi muốn gửi lời cảm đến các Thầy, Cô trong khoa Công nghệ
thông tin- Trường Đại học Công nghệ - Đại học Quốc gia Hà nội đã truyền đạt
các kiến thức quý báu cho tôi trong suốt thời gian học tập tại trường. Đặc biệt,
tôi xin gửi lời cảm ơn sâu sắc tới cô giáo hướng dẫn TS Hồ Cẩm Hà, người đã
tận tình chỉ bảo và hướng dẫn về mặt chuyên môn cho tôi trong suốt quá trình
thực hiện luận văn này.
Cũng qua đây, tôi xin gửi lời cảm ơn đến Ban Giám hiệu trường THPT
Chuyên Đại học Sư phạm Hà Nội, nơi tôi đang công tác đã tạo mọi điều kiện
thuận lợi cho tôi trong thời gian học tập cũng như trong suốt quá trình thực
hiện luận văn tốt nghiệp.
Cuối cùng, tôi xin cảm ơn gia đình, bạn bè, đồng nghiệp đã luôn ủng hộ,
động viên tôi rất nhiều để tôi yên tâm nghiên cứu và hoàn thành luận văn.
Trong suốt quá trình làm luận văn, bản thân tôi đã cố gắng tập trung tìm hiểu,
nghiên cứu và tham khảo thêm nhiều tài liệu liên quan. Tuy nhiên, do thời gian
hạn chế và bản thân còn chưa có nhiều kinh nghiệm trong nghiên cứu khoa học,
chắc chắn bản luận văn vẫn còn nhiều thiếu sót. Tôi rất mong được nhận sự chỉ
bảo của các Thầy Cô giáo và các góp ý của bạn bè, đồng nghiệp để luận văn
được hoàn thiện hơn.
Hà Nội, ngày 12 tháng 06 năm 2011
Nguyễn Thị Chinh
Trang 4
MỤC LỤC
LỜI NÓI ĐẦU 7

2. Lịch sử của mô phỏng thuật toán 32
3. Hiệu quả của mô phỏng thuật toán trong giảng dạy 34
4. Một số yêu cầu đối với mô phỏng thuật toán 38
4.1. Mô phỏng đúng theo thuật toán 38
4.2. Cho phép thực hiện theo từng bước 38
4.3. Mô phỏng thuật toán phải có tính động 38
4.4. Có thể thực thi với mọi bộ dữ liệu đầu vào 40
4.5. Có sự phân cấp người học 40
5. Quy trình mô phỏng thuật toán 40
5.1. Nghiên cứu và phân tích giải thuật 40
5.2. Mô phỏng dữ liệu vào và kết quả đầu ra 41
5.3. Chia thuật toán thành nhiều bước nhỏ rồi mô phỏng theo từng bước 42
5.4. Tổng hợp mô phỏng theo các bước 44
5.5. Sơ đồ cấu trúc chung của hệ thống mô phỏng 44
Trang 5
6. Đề xuất lựa chọn công cụ để phát triển chương trình mô phỏng thuật toán 45
6.1. Một số hệ thống mô phỏng thuật toán chung 46
6.2. Sử dụng công cụ mô phỏng thuật toán riêng biệt 50
6.3. Xây dựng hệ thống từ đầu 51
Chương 3 PHÂN TÍCH THIẾT KẾ HỆ THỐNG MÔ PHỎNG MỘT SỐ
THUẬT TOÁN TRÊN ĐỒ THỊ 52
1. Mục đích 52
2. Những yêu cầu thực tế 52
3. Đề xuất cho hệ thống mới 53
4. Thiết kế hệ thống mô phỏng một số thuật toán trên đồ thị 54
4.1. Lựa chọn công cụ lập trình 55
4.2. Chức năng mô phỏng của các thuật toán được cài đặt 57
4.2.1 Mô phỏng thuật toán tìm kiếm 57
4.2.2. Mô phỏng thuật toán Dijkstra 59
4.2.3. Mô phỏng thuật toán Ford – Bellman 61

các thuật toán đó đòi hỏi thời gian và công sức rất lớn. Hiện nay, việc truyền đạt
các thuật toán trên đồ thị cho học sinh chuyên Tin gặp rất nhiều khó khăn. Có
nhiều rất nhiều lý do: Các thuật toán đó khó hình dung, việc tổ chức dữ liệu cho
nó cũng phức tạp, thời gian giảng dạy trên lớp có hạn, tài liệu tham khảo có thể
tự đọc, tự học vẫn còn ít….
Trong khuôn khổ đề tài này, chúng tôi xây dựng một chương trình nhằm
mô phỏng hoạt động của ba thuật toán giải ba bài toán cơ bản trên đồ thị theo
phân phối chương trình của Bộ Giáo dục với hai mục đích: để học sinh có thể dễ
dàng nắm bắt tư tưởng cũng như từng bước hoạt động cụ thể của các thuật toán,
để giáo viên có thể làm cho bài giảng về các thuật toán này trở nên dễ hiểu, dễ
tiếp thu hơn.
Nội dung luận văn được chia thành 3 chương:
Trang 7
Chương I. Những kiến thức cơ bản về thuật toán.
Ở chương này, chúng tôi trích nêu khái niệm về bài toán và thuật toán.
Các tính chất của thuật toán, xác định độ phức tạp của thuật toán…Cuối cùng,
chúng tôi giới thiệu ba thuật toán quan trọng trên đồ thị mà học sinh THPT sẽ
được học.
Chương II. Mô phỏng thuật toán.
Chương này chúng tôi trình bày khái niệm mô phỏng, các chức năng của
mô phỏng và các vấn đề liên quan như: lịch sử mô phỏng, nghiên cứu về hiệu
quả của nó trong giảng dạy và một số yêu cầu đối với việc mô phỏng thuật toán
nói chung.
Chương III. Phân tích thiết kế hệ thống mô phỏng một số thuật toán trên
đồ thị.
Ở chương 3, chúng tôi trình bày về quá trình phân tích, thiết kế và xây
dựng hệ thống mô phỏng trên ba thuật toán: thuật toán tìm kiếm (tìm kiếm theo
chiều sâu và tìm kiếm theo chiều rộng), thuật toán tìm đường đi ngắn nhất (thuật
toán Dijsktra) và thuật toán tìm cây khung cực tiểu trên đồ thị vô hướng có trọng
số (thuật toán Prim)…

- Nếu N = 1 thì thông báo là N không nguyên tố rồi kết thúc;
- Nếu 1< N < 4 thì thông báo N là số nguyên tố rồi kết thúc;
- Nếu N ≥ 4 và không có ước trong khoảng từ 2 đến
][ N
thì N là nguyên
tố.
Thuật toán: Có nhiều cách mô phỏng khác nhau. Dưới đây là cách
mô phỏng thuật toán dạng liệt kê các bước:
Bước 1. Nhập số nguyên dương N;
Bước 2. Nếu N = 1 thì thông báo là N không nguyên tố rồi kết thúc;
Bước 3. Nếu N < 4 thì thông báo N là số nguyên tố rồi kết thúc;
Bước 4. i ← 2;
Bước 5. Nếu
(*)
][ Ni >
thì thông báo N là nguyên tố rồi kết thúc;
Bước 6. Nếu N chia hết cho i thì thông báo N không nguyên tố rồi kết
thúc;
Bước 7. i ← i + 1 rồi quay lại bước 5;
3. Các tính chất của thuật toán
Dựa trên khái niệm về thuật toán và ví dụ ở trên ta thấy các thao tác trong
thuật toán phải được mô tả đủ chi tiết để một đối tượng cứ tiến hành thực hiện
theo đúng thứ tự các thao tác đó là có thể cho ra output dựa trên input tương
ứng. Một thuật toán phải đảm bảo được các tính chất sau:
Tính xác định: Sau khi thực hiện một thao tác thì hoặc là thuật toán kết
thúc hoặc là có đúng một thao tác xác định để thực hiện tiếp theo.
Trang 10
Tính đúng đắn: Sau khi thực hiện thuật toán ta phải nhận được đúng
Output cần tìm.
Tính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện.

chương trình nguồn sẽ thực hiện bao nhiêu lần trên một tập dữ liệu vào. Việc
đánh giá đó không chỉ đánh giá, so sánh trong việc lựa chọn thuật toán mà còn
có thể hiệu chỉnh, cải tiến thuật toán đã có tốt hơn. Khi đánh giá thời gian thực
hiện thuật toán ta chú ý đặc biệt đến các phép toán mà số lần thực hiện không ít
hơn các phép toán khác – ta gọi là phép toán tích cực của thuật toán.
Cách đánh giá thời gian thực hiện thuật toán độc lập với hệ thống máy
tính dẫn đến khái niệm về Độ phức tạp của thuật toán. Thời gian thực hiện một
thuật toán bằng chương trình máy tính phụ thuộc vào rất nhiều yếu tố. Một yếu
tố cần chú ý nhất đó là kích thước của dữ liệu đầu vào. Dữ liệu càng lớn thì thời
gian xử lý càng chậm. Nếu gọi n là kích thước dữ liệu đưa vào thì thời gian thực
hiện của một thuật toán có thể biểu diễn một cách tương đối như một hàm của n:
T(n). Thực tế, T(n) không những chỉ phụ thuộc vào kích thước n mà còn phụ
thuộc vào đặc tính, tình trạng thực tế của bộ dữ liệu đầu vào.
Ví dụ, với thuật toán sắp xếp dãy số đã cho thành dãy tăng dần thì thời
gian sắp xếp còn phụ thuộc vào dãy đầu vào đã là dãy tăng dần, dãy được sinh
ngẫu nhiên hay được sắp xếp theo thứ tự ngược lại. Vì thế cần phải xem xét các
trường hợp tốt nhất, trung bình và xấu nhất. [Xem 2]
Việc xác định độ phức tạp của một thuật toán bất kỳ có thể rất phức tạp.
Tuy nhiên, trong thực tế, đối với một số thuật toán ta có thể phân tích bằng một
số quy tắc đơn giản:
4.1. Quy tắc max
Trang 12
Nếu thuật toán T có thời gian thực hiện T(n) =O(f(n)+g(n)) thì có thể coi
T có độ phức tạp là O(max(f(n), g(n)))
4.2. Quy tắc tổng
Nếu thuật toán T gồm hai đoạn thuật toán liên tiếp T1 và T2 và nếu T1 có
thời gian thực hiện T1(n) = O(f(n)), T2 có thời gian thực hiện là T2(n) = O(g(n))
thì thời gian thực hiện T sẽ là:
T(n) = T1(n) + T2(n) = O(f(n)+ g(n))
4.3. Quy tắc nhân

N
logN NlogN N
2
N
3
2
n
1
0
0
1
1
2
2
1
2
4
8
4
4
2
8
16
64
16
8
3
24
64
512

n
, x
nhập từ bàn phím.
Thuật toán 1:
1.Input n, a
0
, a
1
,a
2
,…a
n
, x;
2. S:=a
0
;
3.for i := 1 to n do begin
3.1 p:=1;
3.2 for j := 1 to i do p:= p*x;
3.3 S:= S+a
i
*p;
End;
4. Output s;
Với mỗi giá trị i của vòng lặp 3, vòng lặp 3.2 thực hiện i vòng lặp nên khi
n = i nó thực hiện đủ n vòng lặp. Vậy vòng lặp 3 thực hiện
2
)1( −nn
lần câu lệnh
sau do nên thời gian tính toán tỉ lệ thuận với n

End;
4. Output S;
Hai lệnh 2 và 4 đều có độ phức tạp tính toán là O(1). Vòng lặp 3 cần thực
hiện n lần hai thao tác tính S và p.Vậy số lần thực hiện lệnh 3 là 2n. Do vậy, độ
phức tạp tính toán của thuật toán trên là O(n).
5. Chi phí thực hiện thuật toán
Khái niệm độ phức tạp tính toán đặt ra là để đánh giá chi phí thực hiện
một thuật toán về mặt thời gian. Nhưng chi phí thực hiện thuật toán còn có rất
nhiều yếu tố khác nữa: không gian bộ nhớ phải sử dụng là một ví dụ. Tuy nhiên,
trên phương diện phân tích lý thuyết, ta chỉ có thể xét tới vấn đề thời gian bởi
việc xác định các chi phí khác nhiều khi rất mơ hồ và phức tạp. Đối với người
lập trình thì khác, một thuật toán với độ phức tạp dù rất thấp cũng sẽ là vô dụng
nếu như không thể cài đặt được trên máy tính, chính vì vậy khi bắt tay cài đặt
một thuật toán, ta phải biết cách tổ chức dữ liệu một cách khoa học, tránh lãng
phí bộ nhớ không cần thiết. Có một quy luật tương đối khi tổ chức dữ liệu: Tiết
kiệm được bộ nhớ thì thời gian thực hiện thường sẽ chậm hơn và ngược lại. Biết
cân đối, dung hoà hai yếu tố đó là một kỹ năng cần thiết của người lập trình.
[Xem 2]
6. Ba bài toán trên mô hình đồ thị được đưa vào giảng dạy trong trường
Trung học Phổ thông Chuyên
6.1. Một số khái niệm cơ bản về đồ thị
6.1.1. Khái niệm đồ thị (Graph)
Là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Được
mô tả hình thức: G = (V, E). Trong đó:
Trang 15
V gọi là tập các đỉnh (Vertices) và E gọi là tập các cạnh (Edges). Có thể
coi E là tập các cặp (u, v) với u và v là hai đỉnh của V.
Một số hình ảnh của đồ thị:
Đồ thị vô hướng Đồ thị có hướng
6.1.2. Các khái niệm cơ bản

hiệu deg
+
(v) là số cung đi ra khỏi nó; bán bậc vào ký hiệu deg
-
(v) là số cung đi
vào đỉnh đó
Đường đi: Một đường đi độ dài k từ đỉnh u đến đỉnh v là dãy (u = x
0
,
x
1
, , x
k
= v) thoả mãn (x
i
, x
i+1
) ∈ E (là 1 cạnh của đồ thị) với ∀i: (0 ≤ i ≤ k).
Trang 17
1 2
B
3
4
5
Đỉnh u gọi là đỉnh xuất phát, v gọi là đỉnh kết thúc của đường đi. Đường đi
không có cạnh nào đi qua hơn 1 lần gọi là đường đi đơn.
Chu trình: Đường đi có đỉnh xuất phát trùng với đỉnh kết thúc gọi là chu
trình. tương tự ta có khái niệm chu trình đơn.
6.2. Bài toán tìm kiếm trên đồ thị
6.2.1. Phát biểu bài toán

Truy ngược đường đi này sẽ cho ta hành trình đi từ s đến t. Có thể mô tả
thủ tục DFS dạng giả mã như sau:
Procedure DFS(u∈V);
Begin
< 1. Thông báo tới được u >;
< 2. Đánh dấu u là đã thăm>;
< 3. Xét mọi đỉnh v kề với u mà chưa thăm, với mỗi đỉnh v đó >;
Begin
Trace[v] := u; {Truy vết đường đi}
DFS(v); {Gọi đệ quy duyệt bắt đầu với v}
End;
End;
Trang 19
Begin
<Input: đồ thị G, s, t >;
<Khởi tạo: Tất cả các đỉnh đều chưa bị đánh dấu >;
DFS(s);
<Output:
- Nếu t chưa bị đánh dấu thì kết luận: Không có đường từ s->t>;
- Nếu t đã bị đánh dấu thì dựa vào Trace tìm đường đi từ s->t>;
>;
End.
b. Thuật toán tìm kiếm theo chiều rộng BFS (Breadth – First – Search)
Ý tưởng của phương pháp cài đặt này là "lập lịch" duyệt các đỉnh. Khi
thăm một đỉnh ta sẽ lên lịch thăm tất cả các đỉnh kề nó sao cho thứ tự duyệt là
ưu tiên chiều rộng (đỉnh nào gần s hơn sẽ được duyệt trước). Ví dụ: Bắt đầu, ta
thăm đỉnh s. Quá trình thăm S sẽ lên lịch duyệt những đỉnh (u
1
, u
2

, ,
v
q
). Do việc lập lịch như mô tả ở trên nên cần phải xếp hàng cho các đỉnh đã lên
lịch theo đúng thứ tự. Khi thêm đỉnh nào đó ta sẽ thêm vào cuối hàng (vì đỉnh
lên lịch sau chắc chắn xa hơn các đỉnh đã lên lịch (vào hàng) rồi. Chính vì
nguyên tắc đó nên danh sách chứa những đỉnh đang chờ sẽ được tổ chức dưới
dạng hàng đợi (Queue).
Ta sẽ dựng giải thuật như sau:
Bước 1: Khởi tạo: free[s] = true; free[v] = false ∀v ∈V\{s}
First:=1; Last:=1; Queue[Last]:=s;//Queue chỉ chứa s
Bước 2: Lặp cho tới khi Queue rỗng:
u := pop;//lấy u khỏi hàng đợi
Trang 20
free[u]:= false;
Xét ∀v ∈V: nếu v chưa được thăm:
Free[v] = false;//đánh dấu đã thăm
Trace[v] = u;
Push(v);//đẩy v vào hàng đợi, chờ được thăm
Bước 3: Truy vết tìm đường đi hoặc thông báo không thấy đường.
6.2.3. Độ phức tạp tính toán của thuật toán DFS và BFS
Quá trình tìm kiếm trên đồ thị bắt đầu từ một đỉnh có thể thăm tất cả các
đỉnh còn lại, khi đó cách biểu diễn đồ thị [xem 3 – tập 1] có ảnh hưởng lớn tới
chi phí về thời gian thực hiện giải thuật:
Trong trường hợp ta biểu diễn đồ thị bằng danh sách kề, cả hai thuật toán
BFS và DFS đều có độ phức tạp tính toán là O(n + m) = O(max(n, m)). Đây là
cách cài đặt tốt nhất. Nếu ta biểu diễn đồ thị bằng ma trận kề thì độ phức tạp tính
toán trong trường hợp này là O(n + n
2
) = O(n

Thuật toán Ford-Bellman có thể phát biểu rất đơn giản:
Với đỉnh xuất phát S. Gọi d(v) là khoảng cách từ S tới v.
Ban đầu d(S) được khởi gán bằng 0 còn các d(v) với v ≠ S được khởi gán
bằng +∞.
Sau đó ta tối ưu hoá dần các d(v) như sau: Xét mọi cặp đỉnh u, v của đồ
thị, nếu có một cặp đỉnh u, v mà d(v) > d(u) + c(u, v) thì ta đặt lại d(v) := d(u) +
c(u, v). Tức là nếu độ dài đường đi từ S tới v lại lớn hơn tổng độ dài đường đi từ
S tới u cộng với chi phí đi từ u tới v thì ta sẽ huỷ bỏ đường đi từ S tới v đang có
và coi đường đi từ S tới v chính là đường đi từ S tới u sau đó đi tiếp từ u tới v.
Chú ý rằng ta đặt c[u, v] = +∞ nếu (u, v) không là cung. Thuật toán sẽ kết thúc
khi không thể tối ưu thêm bất kỳ một nhãn d[v] nào nữa.
Tính dừng của thuật toán:
Tại bước lặp 0: Bước khởi tạo d(S) = 0; d(v) := +∞ với v ≠ S: thì dãy d(v)
chính là độ dài đường đi ngắn nhất từ S tới v đi qua không quá 0 cạnh
Giả sử tại bước lặp thứ i, d(v) bằng độ dài đường đi ngắn nhất từ S tới v
qua không quá i cạnh, thì do tính chất: đường đi từ S tới v qua không quá i + 1
Trang 22
cạnh sẽ phải thành lập bằng cách: lấy một đường đi từ S tới một đỉnh u nào đó
qua không quá i cạnh, rồi đi tiếp tới v bằng cung (u, v). Nên độ dài đường đi
ngắn nhất từ S tới v qua không quá i + 1 cạnh sẽ được tính bằng giá trị nhỏ nhất
trong các giá trị: (Nguyên lý tối ưu Bellman)
Độ dài đường đi ngắn nhất từ S tới v qua không quá i cạnh
Độ dài đường đi ngắn nhất từ S tới u qua không quá i cạnh cộng với trọng
số cạnh (u, v) (∀u)
Nên sau bước lặp tối ưu các d(v) bằng công thức d(v)
bước i+1
= min(d(v)
bước i
,
d(u)

công thức:
d[v] := min(d[v], d[u] + c[u, v])
Bước lặp sẽ kết thúc khi mà đỉnh đích t được cố định nhãn (tìm được
đường đi ngắn nhất từ s đến t); hoặc tại thao tác cố định nhãn, tất cả các đỉnh tự
do đều có nhãn là +∞ (không tồn tại đường đi).
Có thể đặt câu hỏi, ở thao tác 1, tại sao đỉnh u như vậy được cố định nhãn,
giả sử d[u] còn có thể tối ưu thêm được nữa thì tất phải có một đỉnh t mang nhãn
tự do sao cho d[u] > d[t] + c[t, u]. Do trọng số c[t, u] không âm nên d[u] > d[t],
trái với cách chọn d[u] là nhỏ nhất. Tất nhiên trong lần lặp đầu tiên thì S là đỉnh
được cố định nhãn do d[s] = 0.
Bước 3: Kết hợp với việc lưu vết đường đi trên từng bước sửa nhãn, thông
báo đường đi ngắn nhất tìm được hoặc cho biết không tồn tại đường đi (d[t] =
+∞). Có thể mô tả ngắn gọn thuật toán bằng giả mã như sau:
Bước 1: d[s] = 0 ; d[v] = +∞ (∀v ∈ V\{s}); u = s;
Bước 2: Lặp nếu u ≠ t (với u ∉ S)
Trang 24
2.1. Nếu d[v] > d[u] + c[u,v] thì
d[v] = min{d[v], d[u] + c[u, v]}
trace[v]=u (với v ∉ S - tập các đỉnh đã tối ưu)
2.2 Chọn v có d[v] nhỏ nhất //v=0 không có đường
2.3 Nếu v ≠ 0 thì thêm v vào S; u = v
Bước 3: In ra đường đi tối ưu từ s đến t hoặc thông báo
vô nghiệm.
6.3.4. Độ phức tạp
Nếu đồ thị có nhiều đỉnh, ít cạnh, ta có thể sử dụng danh sách kề kèm
trọng số để biểu diễn đồ thị, tuy nhiên tốc độ của thuật toán Dijkstra vẫn khá
chậm vì trong trường hợp xấu nhất, nó cần n lần cố định nhãn và mỗi lần tìm
đỉnh để cố định nhãn sẽ mất một đoạn chương trình với độ phức tạp O(n). Vậy
độ phức tạp của thuật toán Dijkstra là O(n
2

khoảng cách tới T là +∞. Khi đó đồ thị đã cho không liên thông, ta thông báo
việc tìm cây khung thất bại.
Về mặt kỹ thuật cài đặt, ta có thể làm như sau:
Sử dụng mảng đánh dấu Free. Free[v] = TRUE nếu như đỉnh v chưa bị kết
nạp vào T.
Gọi d[v] là khoảng cách từ v tới T. Ban đầu khởi tạo d[1] = 0 còn d[2] =
d[3] = = d[n] = +∞. Tại mỗi bước chọn đỉnh đưa vào T, ta sẽ chọn đỉnh u nào
ngoài T và có d[u] nhỏ nhất. Khi kết nạp u vào T rồi thì rõ ràng các nhãn d[v] sẽ
thay đổi: d[v]mới := min(d[v]cũ, v[u, v]). Vấn đề chỉ có vậy (chương trình rất
giống thuật toán Dijkstra, chỉ khác ở công thức tối ưu nhãn).
Trang 26
Có thể mô tả thuật toán Prim bằng đoạn giả mã sau:
Bước 1: Khởi tạo: T = {s} d[s] = 0, u = s (s - đỉnh xuất phát)
d[v]=+∞(v ∉ T)
Bước 2: Lặp N-1 lần (N số đỉnh của đồ thị):
2.1 Cập nhật các đỉnh kề với u ở ngoài T
Nếu d[v] > w[u,v]
trace[v] = u, d[v] = w[u,v]
2.2 Chọn v (v ∉ T) mà d[v] nhỏ nhất
Nếu d[v] = +∞ đến bước 3
2.3 Kết nạp v vào T, u = v
Bước 3: In ra cây khung hoặc thông báo vô nghiệm.
6.4.3. Giới thiệu thuật toán Kruskal
Thuật toán Kruskal dựa trên mô hình xây dựng cây khung bằng thuật toán
hợp nhất [xxx], chỉ có điều thuật toán không phải xét các cạnh với thứ tự tuỳ ý
mà xét các cạnh theo thứ tự đã sắp xếp: Với đồ thị vô hướng G = (V, E) có n
đỉnh. Khởi tạo cây T ban đầu không có cạnh nào. Xét tất cả các cạnh của đồ thị
từ cạnh có trọng số nhỏ đến cạnh có trọng số lớn, nếu việc thêm cạnh đó vào T
không tạo thành chu trình đơn trong T thì kết nạp thêm cạnh đó vào T. Cứ làm
như vậy cho tới khi: