tailieunhanh - Cẩm nang thuật toán tập 2 part 5

Tham khảo tài liệu 'cẩm nang thuật toán tập 2 part 5', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 134 TÌM KIẾM THEO t ộ ưu TỈIĨN Ngoài viẹc thay đổi cấu trúc dữ liệu thành hùng đợi ưu tièn chương trình trên giống rác chương trình sữ dụng cho tìm kiếm ròng và sâu vơi hai ngoại lê. Trưức hết can đến một thao tác bổ sung khi cạnh được xét đã nhm trang tập bìa roi vơi tìm kiếm rộng và sâu các cạnh như thế được bỏ qua nhưng trong chương trình trên ta càn phải kiểm tra xem cạnh mới có làm giâm độ ưu tièn hay không. ĐỈẾU này bâo đảm chúng ta luôn xét đến đình kế tiếp trong tập bìa thỏa đíèu kiện gàn với cây nhất như mong muốn. Thứ dến chương trinh này giữ vết của cây một cách tương minh băng cách duy trì màng dad mảng lưu trữ cha của mỗi nút trong cây tìm kiếm ưu tièn tên của nút khiến cho nút đó được dưa từ tập bìa vào tập cày . Cũng thế với mỗi nút A trên cây val k là trọng số của cạnh nôì giữa k và dad k . Các đinh trong tập bìa được đánh dấu bằng các trong số âm như ở phần trưóc các đỉnh không nhìn thấy được đánh dấu bằng giá trị -unseen thay vì 0. Lý do của sự thay đổi này sẽ trở nên rõ ràng dưới đây. Hình cho thấy kết quâ hoàn tất cùa việc xây dựng cầy bao tràm tối tiểu. Như thương lệ các đỉnh được khoanh trong hình vuông là các đỉnh trên bia các đỉnh được khoanh tròn và có nhãn là các đỉnh trên cây và các đinh được khoanh tròn không nhãn là các đinh không nhìn thấy. Các rạnh ciìa cây là các đương đen dày cạnh có tóng là cạnh ngớn nhất nối mỗi đĩnh trên bia vào cây. Độc già nên 1 0 0 í if 2 IU4 íl ỉ Ẽ ỉ j 2 ÕỊI 01 01 fĩl ữj oj6 Gjs gJ @5 Gjs íĩ 2 Hj ggj gg3 Hj 1 lình Nội tangeite hàngdựi im liên trong tiên trình xày hmg cây bao tràm lóĩ tíéìi 135 1 till11 Kết 1 tiiĩ hoàn tilt cùa viêc xây dựng cây bao trùm tôi tiêĩi theo dõi quá trình tao cây từ hình . Đặc biệt chú ý cách thức nút G được thêm vào cây sau nhiêu bước ờ tập bìa. Đầu tiên khoảng cách từ G đến cây là 6 cạnh GA . Sau khi L được thêm vào cây GL làm cho khoảng cách từ G đến cây chỉ còn 5 sau đó E lại được thêm vào cây nên khoáng cách chỉ còn 1 và G được thêm vào cây .