Topological Sort là gì

VIỆN ĐÀO TẠO CHẤT LƯỢNG CAO
KHOA CÔNG NGHỆ THÔNG TIN

BÁO CÁO BÀI TẬP
PHÂN TÍCH THIẾT KẾ GIẢI THUẬT
Nhóm 10

Giáo viên hướng dẫn:

Trần Tuấn Anh

Sinh viên

MSSV

Nguyễn Ngọc Trung

19H1120061

Đào Văn Thương

19H1120035

THÀNH PHỐ HỒ CHÍ MINH
1|Page


MỤC LỤC

PHẦN I: LỜI NÓI ĐẦU.3
PHẦN II: SẮP XẾP TOPO4

1.
2.
3.
4.

GIỚI THIỆU VỀ SẮP XẾP TOPO4
MƠ TẢ VÀ PHÂN TÍCH ĐỘ PHỨC TẠP...5
CODE MẪU..11
KẾT LUẬN VÀ ĐÁNH GIÁ13

PHẦN III: GIẢI THUẬT DJIKSTRA.14
1.
2.
3.
4.

GIỚI THIỆU VỀ GIẢI THUẬT DJIKSTRA14
MƠ TẢ VÀ PHÂN TÍCH ĐỘ PHỨC TẠP...15
CODE MẪU...25
KẾT LUẬN VÀ ĐÁNH GIÁ.27

2|Page


PHẦN I: LỜI NÓI ĐẦU

Lý thuyết đồ thị là một lĩnh vực nghiên cứu đã có từ lâu đờivà có nhiều ứng
dụng hiện đại.Những tư tưởng cơ bản của lý thuyết đồ thị đươc đề xuất từ những năm
đầu của thế kỷ 18 bởi nhà toán học lỗi lạc người Thụy Sĩ Leonhard Euler.Chính ơng là
người đã sử dụng đồ thị để giải bài toán nổi tiếng về các cái cầu ở thàng phố

Konigsberg. Đồ thị được sử dụng để giải quyết các bài toán trong nhiều lĩnh vực khác
nhau .Chẳng hạn , đồ thị có thể sử dụng để xác định các mạch vịng trong vấn đề giải
tích mạch điện.Chúng ta có thể phân biệt các hợp chất hố học hữu cơ khác nhau với
cùng công thức phân tử nhưng khác nhau về cấu trúc phân tử nhờ đồ thị.Chúng ta có
thể xác định xem hai máy tính trong mạng có thể trao đổi thơng tin được với nhau hay
khơng nhờ mơ hình đồ thị của mạng máy tính. Đồ thị có trọng số trên các cạnh có thể
sử dụng để giải các bài tốn như : tìm đường đi ngắn nhất giữa hai thành phố trong
cùng một mạng giao thơng . Chúng ta cịn sử dụng đồ thị để giải các bài toán về lập
lịch,thời khoá biểu,và phân bố tần số cho các trạm phát thanh và truyền hình.... Mục
đích ta tìm hiểu là nhằm giới thiệu các khái niệm cơ bản,các bài toán ứng dụng quan
trọng của lý thuyết đồ thị như bài toán cây khung nhỏ nhất , bài tốn tìm đường đi
ngắn nhất... và những thuật tốn để giải quyết chúng đã được trình bày chi tiết cùng
với việc phân tích và hướng dẫn cài đặt chương trình trên máy tính.

3|Page


PHẦN II: SẮP XẾP TOPO
1. GIỚI THIỆU VỀ SẮP XẾP TOPO:
- Thông thường đối với một công việc lớn bao giờ ta cũng cần phải chia nó
thành nhiều phần để thực hiện. Có những phần việc có thể thực hiện được
độc lập nhưng cũng có những phần việc chỉ thực hiện được khi một số phần
việc khác đã được làm xong.
- Sắp xếp topo [topological sorting] là một trong những bài tốn có tính ứng
dụng cao cả trong Tin học lẫn Toán học và đời sống thường ngày. Đây là quá
trình sắp xếp một dãy các phần tử sao cho thứ tự mới vẫn đảm bảo được thứ
tự cục bộ [một cách nơm na có nghĩa là thứ tự được xác định đối với một vài
cặp phần tử chứ không phải là tất cả các phần tử] vốn có của chúng. Nhờ sắp
xếp topo mà ta có thể tính được thời gian tối thiểu để thực hiện một chuỗi
các công việc.


- Ý tưởng sắp xếp topo là dựa trên DFS [tìm kiếm theo độ sâu]. Điều kiện để
thực hiện topological sorting đó là DAG [đồ thị khơng có chu trình]. Thực
tế, thơng qua việc sắp xếp, ta có thể kiểm tra xem đồ thị đó có chứa chu trình
hay khơng. Một đồ thị khơng có chu trình sẽ có ít nhất 1 sắp xếp topo.

- VD: Trong một số trường ĐH ở VN hiện nay, có những học phần gọi là học
phần tiên quyết mà sinh viên buộc phải hoàn thành trước khi học các học
phần khác. Nếu học phần v là học phần tiên quyết đối với học phần w, kí
hiệu là u