Thuật toán sẽ xây dựng dựng tập cạnh T của cây khung bé dại nhất H= theo từng bước như sau:

1. Sắp xếp các cạnh của trang bị thị G theo đồ vật tự tăng cao của trọng số cạnh;

2. Khởi đầu từ tập cạnh T=φ, sinh sống mỗi bước, ta đang lần lượt thông qua trong danh sách các cạnh vẫn được sắp tới xếp, từ cạnh gồm trọng số bé dại đến cạnh bao gồm trọng số mập để tìm thấy cạnh mà lại khi bổ sung cập nhật nó vào T không chế tạo ra thành quy trình trong tập các cạnh đã được bổ sung cập nhật vào T trước đó;

3. Thuật toán sẽ hoàn thành khi ta thu được tập T bao gồm n-1 cạnh.

Bạn đang xem: Thuật toán kruskal tìm cây khung nhỏ nhất

Thuật toán được tế bào tả trải qua thủ tục Kruskal như sau:

void Kruskal(void){ T = φ; While(| T | trọng lượng tính toán những nhất cảu thuật toán chủ yếu là ở bước sắp xếp các cạnh của đồ thị theo sản phẩm công nghệ tự không giảm của độ dài những cạnh để bổ sung vào cây khung. Đối với đồ thị độ lớn m cạnh thì cần phải tiến hành cỡ m*logm phép toán để sắp xếp. Tuy nhiên, để kiến thiết cây khung nhỏ dại nhất với n-1 cạnh, ta không nên sắp xếp toàn thể mà chỉ cần xét phần trên cảu dãy đó. Để có tác dụng việc đó ta hoàn toàn có thể sử dụng những thủ tục thu xếp vun đống (Heap sort).

Trong thuật toán Kruskal bài toán lựa chọn cạnh để xẻ xung đòi hỏi phải gồm một thủ tục hiệu quả đế soát sổ tập cạnh T ∪ e có chứa chu trình hay không. Chú ý, các cạnh trong T ở bước lặp trung gian sẽ tạo thành một rừng. Cạnh e bắt buộc khảo sát sẽ khởi tạo thành quy trình với các cạnh vào T khi và chỉ khi cả hai đỉnh đầu của chính nó thuộc và một cây con trong rừng nói trên. Do đó thêm cạnh e vào T không tạo nên thành quy trình khi và chỉ khi nó đề xuất nối 2 cây khác biệt trong T. Một trong những những cách thức hiệu quả để tiến hành việc kiểm soát này là phân hoạch các đỉnh của đồ thị thành các tập bé không giao nhau.

Xem thêm: Câu Hỏi Trắc Nghiệm Vật Lý 12 Có Đáp Án ), 500 Câu Hỏi Trắc Nghiệm Vật Lý 12 Có Đáp Án

Chẳng hạn với đồ thị sau

*

Ta có tập con tất cả 6 tập con một trong những phần tử: 1,2,3,4,5,6. Sau thời điểm bổ xung cạnh có độ dài nhỏ dại nhất 3,5 ta có những tập nhỏ : 1,2,3,5,4,6. Tiếp theo ta thêm cạnh 4,6 ta được những tập nhỏ 1,2,3,5,4,6. Tiếp theo ta thêm canh 4,5 ta được những tập nhỏ 1,2,3,5,4,6. Cạnh có độ dài tiếp sau là 5,6 nhưng bởi hai đầu của nó thuộc và một tập nhỏ 3,5,4,6 buộc phải cạnh 5,6 không được chọn.

Chương trình search cây khung nhỏ dại nhất theo thuật toán Kruskal được thể hiện như sau:


Ma trận ngay cạnh baotrum.in

6 91 2 331 3 172 4 202 3 183 4 163 5 44 5 94 6 85 6 14