Cạnh của cây
Tổng độ dài
Cạnh đã xét

  • Hiện tại
  • Trong cây
  • Sẽ tạo chu trình

Thêm về thuật toán Kruskal

Thuật toán Kruskal

Thuật toán Kruskal xây dựng cây khung nhỏ nhất, tức tập cạnh rẻ nhất nối mọi đỉnh, theo cách đơn giản nhất có thể tưởng tượng: lấy các cạnh từ ngắn nhất đến dài nhất, và giữ lại từng cạnh trừ khi nó sẽ tạo chu trình. Đi từng bước để xem các phần riêng biệt lớn dần và gộp thành một cây, cùng những cạnh bị bỏ qua. Nhấn Phát để xem cây lớn dần, hoặc dùng Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu. Số trên mỗi cạnh là độ dài của cạnh. Dưới đồ thị là các cạnh còn chờ thử, từ ngắn nhất đến dài nhất; cạnh nào có hai đầu đã được nối với nhau sẽ tạo chu trình và được vẽ nét đứt màu đỏ. Đồ thị mới tạo một đồ thị khác; chọn số đỉnh và số cạnh. Khi bảng đang được chọn, phím mũi tên đi từng bước, phím cách phát và tạm dừng, còn Home và End nhảy về đầu và cuối.

Cách nó hoạt động

  1. Nhấn Phát, hoặc dùng Bước và Lùi để đi từng bước.
  2. Kéo thanh trượt bước để nhảy đến bất kỳ đâu. Các cạnh còn chờ thử được liệt kê dưới đồ thị, ngắn nhất đứng đầu.
  3. Để ý các cạnh vẽ nét đứt màu đỏ: chúng sẽ tạo chu trình. Đồ thị mới tạo một đồ thị khác để thử.

Thuật toán Kruskal hoạt động thế nào

Sắp xếp mọi cạnh từ ngắn nhất đến dài nhất. Ban đầu mỗi đỉnh là một phần riêng. Thử các cạnh theo thứ tự: nếu một cạnh nối hai phần khác nhau, nó được đưa vào cây và hai phần trở thành một; nếu hai đầu của nó đã ở cùng một phần, nó sẽ tạo chu trình, nên bỏ qua. Dừng khi tất cả đã thành một phần, điều này xảy ra sau khi có ít hơn số đỉnh một cạnh, thường rất lâu trước khi thử đến cạnh cuối cùng.

Union-find

Với mỗi cạnh, thuật toán Kruskal phải hỏi hai đầu của nó đã được nối với nhau chưa. Cấu trúc union-find trả lời nhanh câu hỏi đó: mỗi phần có một đỉnh đại diện, find đi theo các liên kết đến đại diện, còn union nối đại diện này với đại diện kia. Với hai mẹo đơn giản, nén đường đi và hợp theo kích thước, mỗi câu hỏi gần như chỉ mất thời gian hằng số, nên sắp xếp các cạnh là phần chậm nhất, với khối lượng công việc tăng theo E log E.

Câu hỏi thường gặp

Thuật toán Kruskal là gì?

Một thuật toán tham lam xây dựng cây khung nhỏ nhất bằng cách sắp xếp mọi cạnh từ ngắn nhất đến dài nhất và thêm từng cạnh không tạo chu trình với các cạnh đã chọn.

Thuật toán Kruskal phát hiện chu trình thế nào?

Một cạnh tạo chu trình đúng khi hai đầu của nó đã được nối với nhau bởi các cạnh đã chọn. Cấu trúc union-find theo dõi những đỉnh nào đã được nối và trả lời câu hỏi đó gần như tức thì.

Vì sao thuật toán Kruskal đúng?

Nhờ tính chất chu trình: cạnh dài nhất trên bất kỳ chu trình nào cũng không bao giờ cần cho cây khung nhỏ nhất. Mọi cạnh Kruskal bỏ qua đều là cạnh dài nhất trên chu trình mà nó sẽ tạo, vì mọi cạnh trước nó đều ngắn hơn hoặc bằng.

Khi nào nên dùng Kruskal thay vì Prim?

Thuật toán Kruskal đơn giản và nhanh trên đồ thị thưa, và làm việc trực tiếp trên một danh sách cạnh thông thường. Thuật toán Prim hợp với đồ thị dày và đồ thị lưu dưới dạng danh sách kề. Cả hai đều tìm được cây có cùng tổng độ dài.

Đồ thị của tôi có bị gửi đi đâu không?

Không. Đồ thị được tạo và cây được xây dựng ngay trong trình duyệt của bạn, và cài đặt gần nhất được lưu trong bộ nhớ cục bộ của trình duyệt này.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Tới trình chỉnh sửa