- Hiện tại
- Trong cây
- Kề với cây
- Cạnh tốt nhất hiện có
Thuật toán Prim
Thuật toán Prim xây dựng cây khung nhỏ nhất, tức tập cạnh rẻ nhất nối mọi đỉnh, bằng cách phát triển một cây duy nhất từ điểm xuất phát. Ở mỗi bước, nó thêm đỉnh có thể đến được bằng cạnh ngắn nhất từ cây. Nhấp vào một đỉnh để bắt đầu từ đó và đi từng bước để xem các đỉnh đang chờ, cạnh tốt nhất của chúng và cây lớn dần. 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. Nhấp vào một đỉnh để chọn làm điểm xuất phát: cây sẽ lớn dần từ đó. Số trên mỗi cạnh là độ dài của cạnh. Dưới đồ thị là các đỉnh đang chờ gia nhập, mỗi đỉnh kèm độ dài cạnh tốt nhất nối nó với cây, cạnh này được vẽ nét đứt. Đồ 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
- Nhấp vào một đỉnh để chọn làm điểm xuất phát: cây sẽ lớn dần từ đó.
- 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.
- Theo dõi các đỉnh đang chờ dưới đồ thị, mỗi đỉnh kèm cạnh tốt nhất nối nó với cây. Đồ thị mới tạo một đồ thị khác để thử.
Thuật toán Prim hoạt động thế nào
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 nối nó với cây, nếu có. Lặp lại: lấy đỉnh có cạnh ngắn nhất, thêm đỉnh đó và cạnh đó vào cây, rồi xét các cạnh của nó: nếu một cạnh ngắn hơn cạnh tốt nhất hiện có của một đỉnh kề, cạnh đó trở thành cạnh tốt nhất của đỉnh kề ấy. Khi mọi đỉnh đã gia nhập, cây có ít hơn số đỉnh một cạnh, và tổng độ dài nhỏ nhất có thể.
Prim và Dijkstra
Thuật toán Prim và thuật toán Dijkstra trông gần như giống nhau: cả hai đều mở rộng một vùng từ điểm xuất phát và giữ các đỉnh đang chờ trong hàng đợi ưu tiên. Khác biệt nằm ở con số trong hàng đợi. Dijkstra giữ toàn bộ khoảng cách của mỗi đỉnh từ điểm xuất phát; Prim chỉ giữ độ dài của một cạnh tốt nhất nối nó với cây. Vì vậy Dijkstra xây dựng cây đường đi ngắn nhất, còn Prim xây dựng cây có tổng độ dài nhỏ nhất, và hai cây này thường khác nhau.
Câu hỏi thường gặp
Thuật toán Prim là gì?
Một thuật toán tham lam xây dựng cây khung nhỏ nhất của đồ thị có trọng số bằng cách phát triển một cây từ một đỉnh xuất phát, luôn thêm cạnh ngắn nhất nối cây với một đỉnh bên ngoài.
Đỉnh xuất phát có quan trọng không?
Chỉ ảnh hưởng đến thứ tự: từ điểm xuất phát nào, thuật toán Prim cũng kết thúc với một cây khung có cùng tổng độ dài nhỏ nhất. Khi một số cạnh dài bằng nhau, bản thân cây có thể khác.
Ai đã phát minh ra thuật toán Prim?
Vojtěch Jarník mô tả nó đầu tiên, năm 1930. Robert Prim tìm lại nó năm 1957 và Edsger Dijkstra năm 1959, nên nó còn được gọi là thuật toán Jarník hay thuật toán Prim–Jarník.
Thuật toán Prim nhanh đến mức nào?
Với heap nhị phân, khối lượng công việc tăng theo E log V với V đỉnh và E cạnh. Nếu dùng một mảng đơn giản thay cho heap thì mất khoảng V² bước, tốt hơn cho đồ thị dày, nơi gần như mọi cặp đỉnh đều được nố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