Bài toán cây khung cực tiểu Quizz

Trọng số của cạnh

Cạnh có tạo chu trình hay không

Tổng bậc của đồ thị

Cạnh có nối 2 đỉnh trong cùng thành phần hay không

Cạnh bất kỳ

Cạnh có trọng số nhỏ nhất nối từ cây hiện tại đến đỉnh chưa xét

Cạnh có trọng số lớn nhất

Cạnh tạo chu trình

n

n−1

Phụ thuộc số cạnh ban đầu

n+1

Cây tìm kiếm nhị phân

Union-Find (Disjoint Set Union - DSU)

Danh sách kề

Danh sách liên kết

Cạnh xuất phát từ đỉnh có tên đứng trước trong bảng chữ cái

Cạnh bất kỳ vì kết quả không thay đổi

Cạnh nối tới đỉnh có bậc cao hơn

Cạnh nối tới đỉnh nằm gần gốc cây hơn

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

Vẫn là cây khung

Tạo thêm chu trình

Tăng số cạnh lên

DFS

Prim

BFS

Kruskal

Đỉnh có trọng số nhỏ nhất

Cạnh có trọng số nhỏ nhất

Đỉnh bất kỳ

Đỉnh xa nhất trong đồ thị

6

7

5

9

Không thêm cạnh đó vào cây

Gộp hai tập lại

Gán lại trọng số

Đánh dấu là "chu trình chính"

Kruskal có thể áp dụng cho đồ thị không liên thông, thu được kết quả một rừng khung cực tiểu

Nếu đồ thị có nhiều cạnh trọng số bằng nhau, cây khung cực tiểu có thể không duy nhất

Prim không tạo được cây khung nếu đồ thị có chu trình

Cây khung không bao giờ có chu trình

Tìm chu trình Hamilton

Dùng thuật toán Dijkstra

Dùng BFS

Dùng cây khung cực tiểu

Prim dùng hàng đợi ưu tiên, Kruskal dùng sắp xếp cạnh

Kruskal có thể áp dụng cho đồ thị không liên thông để tìm rừng khung

Prim không bao giờ tạo chu trình nếu dùng đúng

Kruskal cần khởi tạo điểm gốc

{AB, BD, DC, DE}

{AB, AC, CE, DE}

{AB, BC, CD, CE}

{AB, BC, CD, CE, DE}