�ݺ�ߣ

- Bắt đầu tại một đỉnh A bất kì
của đồ thị G gồm n đỉnh, ta tìm
một đỉnh gần đỉnh A nhất trong
số các đỉnh có đường đi từ đỉnh
A, giả sử đỉnh đó là đỉnh B
2

- Từ những đỉnh có đường đi từ
đỉnh A và từ đỉnh B, ta lại chọn một
đỉnh gần đỉnh A hoặc gần đỉnh B
nhất sao cho không tạo nên chu
trình, giả sử đỉnh tìm được là đỉnh C
- Quá trình tiếp tục như vậy cho đến
khi không tìm được đỉnh nào thỏa
mãn. Kết quả thu được là cây khung
nhỏ nhất có n đỉnh và n – 1 cạnh
3

1
2
3
4
8
5 6
109
7
6
9
15
9
12
15
3
5
16
8
17
11
7
2
4

1
2
3
4
8
5 6
109
7
6
9
15
9
12
15
3
5
16
8
17
11
7
2
5

1
2
3
4
8
5 6
109
7
6
9
15
9
12
15
3
5
16
8
17
11
7
2
6

1
2
3
4
8
5 6
109
7
6
9
15
9
12
15
3
5
16
8
17
11
7
2
7

1
2
3
4
8
5 6
109
7
6
9
15
9
12
15
3
5
16
8
17
11
7
2
8

1
2
3
4
8
5 6
109
7
6
9
15
9
12
15
3
5
16
8
17
11
7
2
9

1
2
3
4
8
5 6
109
7
6
9
15
9
12
15
3
5
16
8
17
11
7
2
10

1
2
3
4
8
5 6
109
7
6
9
15
9
12
15
3
5
16
8
17
11
7
2
11

1
2
3
4
8
5 6
109
7
6
9
15
9
12
15
3
5
16
8
17
11
7
2
12

1
2
3
4
8
5 6
109
7
6
9
15
9
12
15
3
5
16
8
17
11
7
2
13

1
2
3
4
8
5 6
109
7
6
9
15
9
12
15
3
5
16
8
17
11
7
2
14

1
2
3
4
8
5 6
109
7
6
9
15
9
12
15
3
5
16
8
17
11
7
2
15

1
2
3
4
8
5 6
109
7
6
9
15
9
12
15
3
5
16
8
17
11
7
2
16

1
2
3
4
8
5 6
109
7
6
9
15
9
12
15
3
5
16
8
17
11
7
2
17

1
2
3
4
8
5 6
109
7
6
9
15
9
12
15
3
5
16
8
17
11
7
2
18

1
2
3
4
8
5 6
109
7
6
9
15
9
12
15
3
5
16
8
17
11
7
2
19

1
2
3
4
8
5 6
109
7
6
9
15
9
12
15
3
5
16
8
17
11
7
2
20

1
2
3
4
8
5 6
109
7
6
9
15
9
12
15
3
5
16
8
17
11
7
2
21

- Kiểm tra tính liên thông của đồ
thị: giả sử đồ thị G có n đỉnh, sau
khi thực hiện thuật toán Prime -
tìm cây khung nhỏ nhất kết quả thu
được không đủ n đỉnh thì đồ thị
không liên thông
- Trong giao thông – vận tải: xây
cầu đường, …
22

�ݺ�ߣ

Thuat toan Prim

More Related Content

Thuat toan Prim