1 of 31

HỌC PHẦN

PHÂN TÍCH VÀ THIẾT KẾ THUẬT TOÁN

NÂNG CAO

GIẢNG VIÊN: TS. PHAN ANH CANG

2 of 31

  • Học viên: Nguyễn Thị Bảo Hiền
  • Mã số học viên: 22904003
  • Mã lớp: 0CTT22A

BÁO CÁO CHỦ ĐỀ:

THUẬT TOÁN

MINNIMUM SPANNING TREE

(Tìm cây khung nhỏ nhất trong đồ thị)

3 of 31

NỘI DUNG TRÌNH BÀY

  • Các khái niệm: Đồ thị, đồ thị vô hướng, đồ thị liên thông, chu trình
  • Khái niệm cây khung của đồ thị (Spanning Tree)
  • Bài toán Tìm cây khung nhỏ nhất

(Minnimum Spanning Tree)

  • Ứng dụng của bài toán tìm cây khung nhỏ nhất
  • Thuật toán tìm cây khung nhỏ nhất (Kruskal, Prim)

4 of 31

Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này.

Đồ thị vô hướng là đồ thị mà mỗi cạnh có thể được duyệt qua theo hai hướng.

​

Đồ thị vô hướng, có hướng

Đồ thị vô hướng

Đồ thị có hướng

F

E

B

A

C

D

F

B

A

C

D

E

5 of 31

Đồ thị liên thông là đồ thị trong đó luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó.

Chu trình trong đồ thị là một dây chuyền đóng (có đỉnh đầu trùng đỉnh cuối).

Đồ thị liên thông, chu trình

Đồ thị liên thông, không có chu trình

Đồ thị liên thông, có chu trình

Đồ thị không liên thông

A

D

B

C

F

E

A

F

E

D

B

C

A

D

C

B

E

F

6 of 31

Cây khung (Spanning Tree) của đồ thị G là một đồ thị con của G, chứa tất cả các đỉnh của G, liên thông và không có chu trình.

Khái niệm cây khung (Spanning Tree)

B

A

C

D

Các cây khung có thể được tạo như sau:

B

A

C

D

B

A

C

D

B

A

C

D

B

A

C

D

B

A

C

D

B

A

C

D

B

A

C

D

B

A

C

D

B

A

C

D

B

A

C

D

B

A

C

D

B

A

C

D

B

A

C

D

B

A

C

D

B

A

C

D

B

A

C

D

Ví dụ: Cho đồ thị G có dạng:

7 of 31

Phát biểu bài toán tổng quát:

Tìm cây khung nhỏ nhất 

(Minimum Spanning Tree)

Cho G = (V, E) là đồ thị vô hướng, liên thông với �tập các đỉnh V = {v1, v2, …, vn} và tập các cạnh E = {e1, e2, …, em}

Mỗi cạnh ei∈E được gán một trọng số w(ei)∈R+, w(ei) còn gọi là độ dài cạnh.

Một cây khung (spanning tree) là một đồ thị con của G, liên thông, không có chu trình, và chứa mọi đỉnh của G.

Trọng số của một cây khung là tổng trọng số các cạnh của cây khung đó.

Yêu cầu:

Trong tất cả cây khung của G, tìm cây khung có trọng số nhỏ nhất.

8 of 31

Phát biểu bài toán tổng quát:

Tìm cây khung nhỏ nhất 

(Minimum Spanning Tree)

INPUT: File MST.INP gồm:

- Dòng 1 ghi số đỉnh n và số cạnh m

- M dòng tiếp theo, mỗi dòng ghi 3 giá trị vi, ei, w(ei)

​

OUTPUT: File MST.OUT ghi các cạnh thuộc cây khung nhỏ nhất và trọng số cây khung nhỏ nhất.

9 of 31

Cây khung nhỏ nhất, �trọng số=13

Cho G là đồ thị vô hướng,

liên thông có trọng số, với:

- Tập đỉnh V={A, B,C, D, E, F}

-Tập cạnh E={AB, AC, BC, BD,

BE, CD, CF, DE, DF, EF}

Ví dụ về cây khung nhỏ nhất 

E

B

F

C

D

A

1

2

8

1

9

2

4

3

7

6

E

B

F

C

D

A

1

2

8

1

9

2

4

3

7

6

E

B

F

C

D

A

1

2

8

1

9

2

4

3

7

6

E

B

F

C

D

A

1

2

8

1

9

2

4

3

7

6

E

B

F

C

D

A

1

2

8

1

9

2

4

3

7

6

Cây khung có trọng số=30

Cây khung có trọng số=19

Cây khung có trọng số=14

10 of 31

Ứng dụng của cây khung nhỏ nhất

  • Thiết kế xây dựng hệ thống đường giao thông.
  • Được sử dụng trong giao thức định tuyến mạng máy tính.
  • Thiết kế các mạng như: mạng viễn thông, mạng lưới điện.

11 of 31

Ứng dụng của cây khung nhỏ nhất

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 hai thành phố bất kì luôn có đường đi và tổng chi phí xây dựng là thấp nhất.

Bài toán đặt ra dẫn về bài toán tìm cây khung nhỏ nhất trên đồ thị, trong đó mỗi thành phố ứng với một đỉnh, các cạnh là các tuyến đường nối hai thành phố tương ứng, chi phí xây dựng (tỉ lệ thuận với khoảng cách) là trọng số của các cạnh.

12 of 31

Thuật toán tìm cây khung nhỏ nhất

1. Thuật toán Kruskal

2. Thuật toán Prim

13 of 31

Thuật toán Kruskal

Cho G = (V, E) là đồ thị vô hướng, liên thông với tập các �đỉnh V = {v1, v2, …, vn} và tập các cạnh E = {e1, e2, e3, …, em}

Mỗi cạnh ei∈E có một trọng số w(ei)∈R+ tương ứng.

Gọi T = (V, F) là cây khung nhỏ nhất của G, thuật toán Kruskal xây dựng tập cạnh F của cây khung nhỏ nhất theo từng bước:

Bước 1. Sắp xếp các cạnh ei của đồ thị G theo thứ tự không giảm của w(ei).

Bước 2. Khởi tạo F = {⌀}, mỗi bước ta lấy trong tập E một cạnh theo thứ tự đã được sắp xếp, để bổ sung vào tập F mà không tạo thành chu trình.

Bước 3. Thuật toán kết thúc khi tìm được tập F có đúng n-1 cạnh

14 of 31

Minh hoạ thuật toán Kruskal

  • Cho đồ thị G = (V, E) như hình vẽ. Yêu cầu: Tìm ra cây khung nhỏ nhất của đồ thị G.

E

B

F

C

D

A

1

2

8

1

9

2

4

3

7

6

​

  • Nhận xét: G gồm có n = 6 (đỉnh)

→ Thuật toán Kruskal sẽ dừng khi tập cạnh F của cây khung T = 5.

15 of 31

Minh hoạ thuật toán Kruskal

  • Bước 1: Sắp xếp các cạnh theo thứ tự không giảm trọng số

E

B

F

C

D

A

1

2

8

1

9

2

4

3

7

6

Các cạnh

Trọng số

AB

1

BC

1

AC

2

EF

2

CD

3

BD

4

DE

6

DF

7

BE

8

CF

9

16 of 31

Minh hoạ thuật toán Kruskal

Cạnh đang xét

Tập cạnh F

Kết quả

{AB}

{AB}

​

E

B

F

C

D

A

1

2

8

1

9

2

4

3

7

6

  • Bước 2: Bắt đầu từ tập F = ⌀, mỗi lượt ta lấy trong tập E một cạnh theo thứ tự đã được sắp xếp, để bổ sung vào tập F mà không tạo thành chu trình

Các cạnh

Trọng số

AB

1

BC

1

AC

2

EF

2

CD

3

BD

4

DE

6

DF

7

BE

8

CF

9

17 of 31

  • Bước 2: Bắt đầu từ tập F = ⌀, mỗi lượt ta lấy trong tập E một cạnh theo thứ tự đã được sắp xếp, để bổ sung vào tập F mà không tạo thành chu trình

Cạnh đang xét

Tập cạnh F

Kết quả

{BC}

{AB, BC}

​

​

​

​

​

​

​

​

​

E

B

F

C

D

A

1

2

8

1

9

2

4

3

7

6

Minh hoạ thuật toán Kruskal

Các cạnh

Trọng số

AB

1

BC

1

AC

2

EF

2

CD

3

BD

4

DE

6

DF

7

BE

8

CF

9

18 of 31

Cạnh đang xét

Tập cạnh F

Kết quả

{AC}

{EF}

{AB, BC, EF}

​

​

​

​

​

​

​

​

​

E

B

F

C

D

A

1

2

8

1

9

2

4

3

7

6

  • Bước 2: Bắt đầu từ tập F = ⌀, mỗi lượt ta lấy trong tập E một cạnh theo thứ tự đã được sắp xếp, để bổ sung vào tập F mà không tạo thành chu trình

Minh hoạ thuật toán Kruskal

Các cạnh

Trọng số

AB

1

BC

1

AC

2

EF

2

CD

3

BD

4

DE

6

DF

7

BE

8

CF

9

19 of 31

Cạnh đang xét

Tập cạnh F

Kết quả

{CD}

{AB, BC, EF, CD}

​

​

​

​

​

​

​

​

​

E

B

F

C

D

A

1

2

8

1

9

2

4

3

7

6

  • Bước 2: Bắt đầu từ tập F = ⌀, mỗi lượt ta lấy trong tập E một cạnh theo thứ tự đã được sắp xếp, để bổ sung vào tập F mà không tạo thành chu trình

Minh hoạ thuật toán Kruskal

Các cạnh

Trọng số

AB

1

BC

1

AC

2

EF

2

CD

3

BD

4

DE

6

DF

7

BE

8

CF

9

20 of 31

Cạnh đang xét

Tập cạnh F

Kết quả

{BD}

{AB, BC, EF, CD}

​

​

​

​

​

​

​

​

​

E

B

F

C

D

A

1

2

8

1

9

2

4

3

7

6

  • Bước 2: Bắt đầu từ tập F = ⌀, mỗi lượt ta lấy trong tập E một cạnh theo thứ tự đã được sắp xếp, để bổ sung vào tập F mà không tạo thành chu trình

Minh hoạ thuật toán Kruskal

Các cạnh

Trọng số

AB

1

BC

1

AC

2

EF

2

CD

3

BD

4

DE

6

DF

7

BE

8

CF

9

21 of 31

Cạnh đang xét

Tập cạnh F

Kết quả

{DE}

{AB, BC, EF, CD, DE}

​

​

​

​

​

​

​

​

​

E

B

F

C

D

A

1

2

8

1

9

2

4

3

7

6

  • Bước 2: Bắt đầu từ tập F = ⌀, mỗi lượt ta lấy trong tập E một cạnh theo thứ tự đã được sắp xếp, để bổ sung vào tập F mà không tạo thành chu trình

Minh hoạ thuật toán Kruskal

Các cạnh

Trọng số

AB

1

BC

1

AC

2

EF

2

CD

3

BD

4

DE

6

DF

7

BE

8

CF

9

22 of 31

Cạnh đang xét

Tập cạnh F

Kết quả

{DE}

{AB, BC, EF, CD, DE}

​

​

​

​

​

​

​

​

​

E

B

F

C

D

A

1

2

8

1

9

2

4

3

7

6

  • Bước 3: Thuật toán kết thúc khi tìm được tập F có đúng 5 cạnh

Minh hoạ thuật toán Kruskal

Các cạnh

Trọng số

AB

1

BC

1

AC

2

EF

2

CD

3

BD

4

DE

6

DF

7

BE

8

CF

9

23 of 31

Thuật toán Prim

Gọi T = (V, F) là cây khung nhỏ nhất của G, thuật toán Prim xuất phát từ một đỉnh bất kỳ và từng bước thêm các đỉnh lân cận vào cây khung. Cụ thể:

  • Bước 1: Khởi tạo: F = {⌀}, Vmới = {x}, với x∈V là một đỉnh bất kì.
  • Bước 2: Chọn một đỉnh không thuộc Vmới mà có kết nối với một đỉnh trong Vmới, cạnh tạo từ 2 đỉnh đó phải có trọng số nhỏ nhất. Thêm đỉnh vừa chọn vào Vmới và thêm cạnh vừa chọn vào F.
  • Bước 3: Thuật toán kết thúc khi Vmới = V.

Cho G = (V, E) là đồ thị vô hướng, liên thông với tập các �đỉnh V = {v1, v2, …, vn} và tập các cạnh E = {e1, e2, e3, …, em}

Mỗi cạnh ei∈E có một trọng số w(ei)∈R+ tương ứng.

24 of 31

Minh hoạ thuật toán Prim

  • Cho đồ thị G = (V, E) như hình vẽ. Yêu cầu: Tìm ra cây khung nhỏ nhất của đồ thị G.

​

E

B

F

C

D

A

1

2

8

1

9

2

4

3

7

6

​

  • Nhận xét: G gồm có n = 6 (đỉnh)

→ Thuật toán Prim sẽ dừng khi tập đỉnh V của cây khung T = 6.

25 of 31

Minh hoạ thuật toán Prim

Tập đỉnh VMới

Tập cạnh F

Kết quả

{C}

{⌀}

​

  • Bước 1: Khởi tạo: Vmới = {C}, F = {⌀}

E

B

F

C

D

A

1

2

8

1

9

2

4

3

7

6

26 of 31

Minh hoạ thuật toán Prim

  • Bước 1: Khởi tạo: Vmới = {C}, F = {⌀}
  • Bước 2: Lần lượt chọn đỉnh thêm vào Vmới và cạnh thêm vào F

Cạnh đang xét

Tập đỉnh VMới

Tập cạnh F

Kết quả

{CA, CB, CD, CF}

{C, B}

{CB}

​

E

B

F

C

D

A

1

2

8

1

9

2

4

3

7

6

27 of 31

Minh hoạ thuật toán Prim

  • Bước 1: Khởi tạo: Vmới = {C}, F = {⌀}
  • Bước 2: Lần lượt chọn đỉnh thêm vào Vmới và cạnh thêm vào F

Cạnh đang xét

Tập đỉnh VMới

Tập cạnh F

Kết quả

{CA, CD, CF, BA, BD, BE}

{C, B, A}

{CB, BA}

​

E

B

F

C

D

A

1

2

8

1

9

2

4

3

7

6

28 of 31

Minh hoạ thuật toán Prim

  • Bước 1: Khởi tạo: Vmới = {C}, F = {⌀}
  • Bước 2: Lần lượt chọn đỉnh thêm vào Vmới và cạnh thêm vào F

Cạnh đang xét

Tập đỉnh VMới

Tập cạnh F

Kết quả

{CD, CF, BD, BE}

{C, B, A, D}

{CB, BA, CD}

​

E

B

F

C

D

A

1

2

8

1

9

2

4

3

7

6

29 of 31

Minh hoạ thuật toán Prim

  • Bước 1: Khởi tạo: Vmới = {C}, F = {⌀}
  • Bước 2: Lần lượt chọn đỉnh thêm vào Vmới và cạnh thêm vào F

Cạnh đang xét

Tập đỉnh VMới

Tập cạnh F

Kết quả

{CF, BE, DE, DF}

{C, B, A, D, E}

{CB, BA, CD, DE}

​

E

B

F

C

D

A

1

2

8

1

9

2

4

3

7

6

30 of 31

Minh hoạ thuật toán Prim

  • Bước 1: Khởi tạo: Vmới = {C}, F = {⌀}
  • Bước 2: Lần lượt chọn đỉnh thêm vào Vmới và cạnh thêm vào F

Cạnh đang xét

Tập đỉnh VMới

Tập cạnh F

Kết quả

{CF, DF, EF}

{C, B, A, D, E, F}

{CB, BA, CD, DE, EF}

​

E

B

F

C

D

A

1

2

8

1

9

2

4

3

7

6

  • Bước 3: Thuật toán kết thúc khi Vmới = V.

31 of 31

CẢM ƠN THẦY �VÀ CÁC BẠN �Đà LẮNG NGHE!