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

  • Hiện tại
  • Trong cây
  • Kề với cây
  • Cạnh tốt nhất hiện có
  • Sẽ tạo chu trình

Tìm hiểu thêm về cây khung nhỏ nhất

Cây khung nhỏ nhất

Bạn muốn nối mọi thị trấn bằng cáp, mọi ngôi nhà bằng ống nước, hay mọi máy tính trong một mạng, mà tốn ít vật liệu nhất có thể. Câu trả lời là cây khung nhỏ nhất: tập cạnh nối mọi đỉnh với tổng độ dài nhỏ nhất. Chọn thuật toán Kruskal hoặc Prim và đi từng bước để xem cây lớn dần, mỗi lần thêm một cạnh ngắn nhất được phép. 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. Chọn thuật toán: Kruskal thử các cạnh từ ngắn nhất đến dài nhất, Prim phát triển một cây từ điểm xuất phát; nhấp vào một đỉnh để chọn làm điểm xuất phát của Prim. Số trên mỗi cạnh là độ dài của cạnh. Dưới đồ thị là danh sách các cạnh còn chờ thử, hoặc các đỉnh đang chờ gia nhập cùng độ dài cạnh tốt nhất nối chúng với cây. Đồ 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. Chọn thuật toán Kruskal hoặc Prim. Với Prim, nhấp vào một đỉnh để chọn làm điểm xuất phát.
  2. Nhấn Phát, 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.
  3. Theo dõi các cạnh gia nhập cây và tổng độ dài tăng dần. Đồ thị mới tạo một đồ thị khác để thử.

Thuật toán Kruskal

Sắp xếp tất cả các cạnh từ ngắn nhất đến dài nhất và thử theo thứ tự đó. Nếu một cạnh nối hai phần chưa được nối với nhau, nó được đưa vào cây. Nếu hai đầu của nó đã được nối qua cây, nó sẽ tạo chu trình, nên bị bỏ qua. Dừng lại khi cây có số cạnh ít hơn số đỉnh một. Để biết nhanh hai đỉnh đã được nối hay chưa, thuật toán Kruskal lưu các phần trong một cấu trúc union-find.

Thuật toán Prim

Bắt đầu với một cây chỉ có một đỉnh. Mỗi đỉnh ngoài cây ghi nhớ cạnh ngắn nhất của nó đến cây. Lặp lại việc thêm đỉnh có cạnh ngắn nhất, cùng với cạnh đó, rồi xét các cạnh của đỉnh ấy: một cạnh có thể cho một đỉnh kề đường vào cây ngắn hơn. Thuật toán Prim trông giống thuật toán Dijkstra, nhưng nó so sánh từng cạnh riêng lẻ, chứ không phải cả quãng đường từ điểm xuất phát. Cả hai thuật toán luôn kết thúc với cùng một tổng độ dài.

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

Cây khung nhỏ nhất là gì?

Với một đồ thị liên thông có các cạnh mang độ dài, cây khung là một tập cạnh nối tất cả các đỉnh mà không có chu trình nào; với n đỉnh, nó luôn có n − 1 cạnh. Cây khung nhỏ nhất là cây khung có tổng độ dài nhỏ nhất có thể.

Thuật toán Kruskal và Prim khác nhau thế nào?

Thuật toán Kruskal xét các cạnh của toàn bộ đồ thị từ ngắn nhất đến dài nhất và gộp các phần riêng biệt thành một cây. Thuật toán Prim phát triển một cây duy nhất từ điểm xuất phát, luôn thêm cạnh ngắn nhất đi ra khỏi cây. Cả hai đều tham lam và tìm được cây có cùng tổng độ dài; Kruskal hợp với đồ thị thưa, Prim hợp với đồ thị dày.

Cây khung nhỏ nhất có duy nhất không?

Khi mọi độ dài cạnh đều khác nhau thì có. Khi có những độ dài bằng nhau, có thể có nhiều cây cùng tổng nhỏ nhất, và các thuật toán có thể chọn những cây khác nhau tùy cách xử lý khi hòa.

Cây khung nhỏ nhất có giống đường đi ngắn nhất không?

Không. Cây khung nhỏ nhất giữ cho tổng độ dài của mọi cạnh nhỏ, nhưng đường đi giữa hai đỉnh trong cây có thể dài hơn nhiều so với đường đi ngắn nhất giữa chúng. Để tìm đường đi ngắn nhất, hãy dùng thuật toán Dijkstra.

Đồ 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