Thuật toán Prim - Tìm Cây Khung Nhỏ Nhất

THUẬT TOÁN PRIM

Có bao giờ bao giờ bạn hỏi vì sao giữa các địa điểm trong một thành phố lại có
nhiều đường đi đến như vậy. Vậy có cách nào vừa đảm bảo có đường đi giữa mọi
điểm trong thành phố mà chi phí làm đường lại nhỏ nhất không. Tất nhiên là có
rồi và thuật toán Prim sẽ giúp bạn giải quyế việc đấy một cách dễ dàng.

align="center"
cellpadding="0"
cellspacing="0"
class="tr-caption-container"
style="margin-left: auto; margin-right: auto;"
>



href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj-ycymn95xb9_GAoQz5famCO0MUNHOL15rzP28iZUDw1RW07npWkjyw8xz0AhQnN1u_s8p2K2pGjierFCO1uMi7I1Bq6RuA8LKRivu6syEmMYMGZWNK8_LmujynFwKSYooUwzy_LCBgSQ/s1635/Prim.png"
imageanchor="1"
style="margin-left: auto; margin-right: auto;"
> border="0"
data-original-height="1000"
data-original-width="1635"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj-ycymn95xb9_GAoQz5famCO0MUNHOL15rzP28iZUDw1RW07npWkjyw8xz0AhQnN1u_s8p2K2pGjierFCO1uMi7I1Bq6RuA8LKRivu6syEmMYMGZWNK8_LmujynFwKSYooUwzy_LCBgSQ/s16000/Prim.png"
/>




Thuật toán Prim - Tìm Cây Khung Nhỏ Nhất

THUẬT TOÁN

MÔ TẢ THUẬT TOÁN:

• 
  Bước khởi tạo: Chọn một đỉnh làm gốc sau đó xét đường nối đỉnh gốc
  đến các đỉnh còn lại, nếu không có thì cho khoảng cách vô cùng.
  


• 
  Bước 1.1: Chọn đỉnh có đường nối ngắn nhất đã tìm ở bước trước,
  đánh dấu là đã xét.
  


• 
  Bước 1.2: Xét tiếp đường nối từ đỉnh trên đến các đỉnh còn lại chưa
  xét tới. Nếu phát hiện đỉnh có đường nối ngắn hơn bước trên thì cập nhật
  lại đường nối tại đỉnh đó.
  


• Lặp lại 2 bước trên đến khi đánh dấu hết các đỉnh.

ĐỒ THỊ MẪU:

href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiXt8sSl25uwIuuaOVOgQyvFkcrnwO_Ic0ODPe5MeSg9komZAMiKfE7Y2d_QfPphuItrgu0ISKBE-CKlHgEPMzOf3OrMUKI3G_tuo92-pxitGnhNOrkFDI6Z8LI9kuixAhh8FW6ikz_WSs/s1110/Capture.PNG"
style="margin-left: 1em; margin-right: 1em;"
> border="0"
data-original-height="657"
data-original-width="1110"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiXt8sSl25uwIuuaOVOgQyvFkcrnwO_Ic0ODPe5MeSg9komZAMiKfE7Y2d_QfPphuItrgu0ISKBE-CKlHgEPMzOf3OrMUKI3G_tuo92-pxitGnhNOrkFDI6Z8LI9kuixAhh8FW6ikz_WSs/s16000/Capture.PNG"
/>

MINH HỌA CÁCH GIẢI BẰNG TAY:

href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiE09wM2Y6xiKV3Rx9rXP-2uBKtBK4c6q_PffCGS3FMGtlIOzXLKREstWdp3cUhK6bVWh4nM8seRFysh_aU0vcOwIwh-PWNSuj7Qc0nXlnjUEPbC4d8jId9Ru-d6JFb5a8Bz-OfgsvNfAo/s1143/prim.png"
style="margin-left: 1em; margin-right: 1em;"
> border="0"
data-original-height="390"
data-original-width="1143"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiE09wM2Y6xiKV3Rx9rXP-2uBKtBK4c6q_PffCGS3FMGtlIOzXLKREstWdp3cUhK6bVWh4nM8seRFysh_aU0vcOwIwh-PWNSuj7Qc0nXlnjUEPbC4d8jId9Ru-d6JFb5a8Bz-OfgsvNfAo/s16000/prim.png"
/>

CODE:

KẾT QUẢ:

Minimum Spanning Tree: (6, 2) (6, 3) (6, 4) (4, 5) (1, 6)

Total Weight: 15

CÂY KHUNG NHỎ NHẤT:

href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjTv6-qWVFYWP_E5Vb-W4RGdhlXy709tP1h8btOyEP3v9Hr0PucDX_4zhF4D7L1NBo4FoqMa6XGawuxHqDIJKtAcV80-F3lXoJSybBWoRWRWfrsu8d73MXOuyujolKyGJdkAUuh2vMPXyA/s0/prim.png"
style="display: block; padding: 1em 0px; text-align: center;"
> alt=""
border="0"
data-original-height="657"
data-original-width="1110"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjTv6-qWVFYWP_E5Vb-W4RGdhlXy709tP1h8btOyEP3v9Hr0PucDX_4zhF4D7L1NBo4FoqMa6XGawuxHqDIJKtAcV80-F3lXoJSybBWoRWRWfrsu8d73MXOuyujolKyGJdkAUuh2vMPXyA/s0/prim.png"
/>

LỜI KẾT

Trên đây là những kiến thức mà mình được dạy cũng như là tìm hiểu về thuật
toán Prim, nếu còn gì sai sót các bạn hãy comment ở bên dưới cho mình biết
nhé. Chúc các bạn một tuần làm việc và học tập hiệu quả!

Previous

Next