khóa huấn luyện và đào tạo Lập trình thiết kế C++ kết cấu dữ liệu và lời giải Tìm kiếm cây khung bé dại nhất (Kruskal)
*

Dẫn nhập

Trong bài học trước, họ đã cùng nhau đi tìm kiếm hiểu thuật toán thứ nhất để hoàn toàn có thể tìm cây khung bao gồm trọng số bé dại nhất. Trong bài học ngày hôm nay, bọn họ sẽ xem thêm một thuật toán nữa để hoàn toàn có thể tìm cây khung gồm trọng số bé dại nhất.

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

Nội dung

Để có thể tiếp thu bài học kinh nghiệm này một cách giỏi nhất, các bạn nên gồm những kỹ năng và kiến thức cơ bạn dạng về:

Trong bài học ngày hôm nay, họ sẽ thuộc nhau tìm hiểu về:

Thuật toán Kruskal

Bài toán đặt ra

Ta đang xem lại câu hỏi mà bài học kinh nghiệm trước bọn họ đã để ra:

Một non sông có

*
thành phố được đánh số từ là 1 đến
*
. Hiện tại, chính phủ đang muốn xây dựng các tuyến đường làm thế nào cho từ một thành phố có thể di gửi đến tất cả các thành phố khác. Qua quá trình khảo sát, chính phủ nhận ra có
*
tuyến đường giữa hai thành phố
*
và
*
có thể sản xuất với giá cả là
*
. Nhiệm vụ của doanh nghiệp là đo lường và thống kê chi phí nhỏ dại nhất nhằm xây dựng những tuyến con đường với yêu cầu như trên.

Input:

Dòng 1: 2 số nguyên dương
*
lần lượt diễn đạt số tp và số con đường đường có thể xây dựng
*
Dòng 2…m+1: Mỗi cái gồm tía số nguyên dương
*
trong đó
*
thể hiện mang đến 2 thành phố có thể xây mặt đường kết nối,
*
thể hiện nay cho chi tiêu xây tuyến phố đó
*

Output:

Một số nguyên duy nhất là chi tiêu để xây dựng những tuyến đường làm thế nào để cho từ một thành phố hoàn toàn có thể di chuyển đến toàn bộ các tp khác

Ví dụ:

InputOutput

5 7

1 2 3

2 4 7

3 5 6

4 5 4

2 5 3

1 3 2

2 3 4

12

Giải đam mê ví dụ:

Đây là hình ảnh minh hoạ mang đến ví dụ sinh hoạt trên với các con đường rất có thể xây dựng

*

Đây là các con con đường được chắt lọc (màu cam)

*

Thuật toán Kruskal

Ý tưởng

Ý tưởng căn nguyên của thuật toán Kruskal khá solo giản: ước ao tổng trọng số của cây khung nhưng mà ta chọn nhỏ tuổi nhất thì trọng số của những cạnh mà ta lựa chọn phải bé dại nhất tất cả thể. Vì chưng đó, lúc chọn những cạnh vào cây form ta đã ưu tiên các cạnh có trọng số nhỏ dại trước.

Hãy thử ý tưởng phát minh trên với thiết bị thị dưới đây:

Theo như ý tưởng của ta ở trên, ta vẫn ưu tiên chọn những cạnh gồm trọng số bé dại trước. Vị đó, ta sẽ chọn cạnh nối đỉnh 1 với đỉnh 2 vào cây khung.Tiếp theo, ta sẽ chọn cạnh nối đỉnh 2 với đỉnh 3 vào cây khung. Khi nay, những đỉnh 1, đỉnh 2 với đỉnh 3 liên thông
Theo suôn sẻ tưởng trên, ta sẽ liên tiếp chọn cạnh nối đỉnh 2 cùng đỉnh 3 vào cây khung. Tuy nhiên, ta phân biệt rằng đỉnh 2 cùng đỉnh 3 bây giờ đã liên thông. Vì chưng đó, việc chọn lựa thêm cạnh này vào cây form là vô nghĩa.

Từ thừa nhận xét trên, ta thấy khi lựa chọn cạnh nối sẽ đề nghị kiểm tra xem nhị đỉnh được nối đã liên thông chưa. Vậy thì làm sao để khám nghiệm được điều này? Đây đó là lúc mà ta áp dụng đến cấu trúcDisjoint set Union mà tôi đã giới thiệu

Cách mua đặt

Để bao gồm thể thiết lập thuật toán Kruskal, ta sẽ cần một cấu trúcEdge để lưu trữ những cạnh cùng với 3 biến:

u, v: nhị đỉnh của cạnhw: trọng số của cạnh

Thuật toán ra mắt như sau:

Khởi chế tạo Disjoint set UnionSắp xếp các cạnh theo trọng số tăng đột biến Lần lượt xét các cạnh theo đồ vật tự đã sắp xếp
Nếu như cạnh đó nối hai đỉnh sẽ liên thông thì ta bỏ qua.Nếu như hai đỉnh đó không liên thông thì ta vẫn thêm trọng số cạnh đó vào tác dụng và dùngDisjoint set Union nhằm hợp duy nhất hai tập đựng hai đỉnh
Khi đang xét toàn bộ các cạnh thì đã thu được trọng số của cây khung bao gồm trọng số nhỏ dại nhất

Code

#includeusing namespace std;typedef long long ll;const int Max
N = 1 + 1e5;class Edge { public: int u, v, w; Edge(int _u = 0, int _v = 0, int _w = 0) : u(_u), v(_v), w(_w) bool operator edges;void make_set(int u) parent = u;int find_set(int u) if(u == parent) return u; return parent = find_set(parent);int main() freopen("CTDL.inp","r",stdin); freopen("CTDL.out","w",stdout); cin >> n >> m; for(int i = 0 ; i > u >> v >> w; edges.push_back(Edge(u, v, w)); for(int i = 1 ; i

Độ phức tạp

Ta thấy giá cả lớn độc nhất vô nhị của thuật toán trên nằm tại vị trí khâu sắp tới xếp những cạnh và gồm độ phức tạp là
*
. Do đó, độ tinh vi thời gian của thuật toán là
*
.

Kết luận

Qua bài này họ đã vắt về Tìm tìm cây khung nhỏ dại nhấtvới thuật toán Kruskal

Bài sau họ sẽ tò mò về Tính diện tích s tam giác -Phần 1

Cảm ơn chúng ta đã theo dõi bài bác viết. Hãy nhằm lại phản hồi hoặc góp ý của chính mình để vạc triển bài viết tốt hơn. Đừng quên “Luyện tập – thử thách – không lo khó”.

Thảo luận

Nếu chúng ta có ngẫu nhiên khó khăn hay vướng mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần BÌNH LUẬN bên dưới hoặc trong mục HỎI & ĐÁP trên tủ sách Howkteam.com để cảm nhận sự cung cấp từ cộng đồng.

Lớp 1

Tài liệu Giáo viên

Lớp 2

Lớp 2 - liên kết tri thức

Lớp 2 - Chân trời sáng tạo

Lớp 2 - Cánh diều

Tài liệu Giáo viên

Lớp 3

Lớp 3 - liên kết tri thức

Lớp 3 - Chân trời sáng tạo

Lớp 3 - Cánh diều

Tài liệu Giáo viên

Lớp 4

Sách giáo khoa

Sách/Vở bài bác tập

Tài liệu Giáo viên

Lớp 5

Sách giáo khoa

Sách/Vở bài tập

Tài liệu Giáo viên

Lớp 6

Lớp 6 - kết nối tri thức

Lớp 6 - Chân trời sáng sủa tạo

Lớp 6 - Cánh diều

Sách/Vở bài tập

Tài liệu Giáo viên

Lớp 7

Lớp 7 - kết nối tri thức

Lớp 7 - Chân trời sáng tạo

Lớp 7 - Cánh diều

Sách/Vở bài tập

Tài liệu Giáo viên

Lớp 8

Sách giáo khoa

Sách/Vở bài xích tập

Tài liệu Giáo viên

Lớp 9

Sách giáo khoa

Sách/Vở bài bác tập

Tài liệu Giáo viên

Lớp 10

Lớp 10 - kết nối tri thức

Lớp 10 - Chân trời sáng sủa tạo

Lớp 10 - Cánh diều

Sách/Vở bài bác tập

Tài liệu Giáo viên

Lớp 11

Sách giáo khoa

Sách/Vở bài xích tập

Tài liệu Giáo viên

Lớp 12

Sách giáo khoa

Sách/Vở bài xích tập

Tài liệu Giáo viên

gia sư

Lớp 1

Lớp 2

Lớp 3

Lớp 4

Lớp 5

Lớp 6

Lớp 7

Lớp 8

Lớp 9

Lớp 10

Lớp 11

Lớp 12


*

Cấu trúc tài liệu và giải thuật
Một số định nghĩa về Giải thuật kết cấu dữ liệu mảng (Array)Danh sách links - Linked Lists
Ngăn xếp & Hàng đợi
Một số giải thuật tìm kiếm
Một số lời giải sắp xếp
Cấu trúc tài liệu đồ thị (Graph)Cấu trúc tài liệu cây
Đệ qui (Recursion)Tài liệu xem thêm
Giải thuật Kruskal: search cây khung nhỏ tuổi nhất
Trang trước
Trang sau

Giải thuật Kruskal là gì ?

Giải thuật của Kruskal là kiếm tìm cây khung nhỏ dại nhất dựa trên giải mã tham lam. Giải mã Kruskal xem đồ gia dụng thị như là 1 rừng cây với mỗi nút là 1 trong những cây chưa có người yêu trong rừng. Giải thuật Kruskal không phụ thuộc vào vào điểm bắt đầu. Một cây kết nối với cây khác nếu và chỉ nếu cây này có trọng số (weight - vào chương trước) nhỏ nhất trong số tất cả các cây đã kiếm được và không vi phạm các điểm lưu ý của Cây khung nhỏ tuổi nhất (MST) – trong chương trước.

Để hiểu giải thuật Kruskal, mời chúng ta theo dõi ví dụ như sau:

*

Bước 1: Xóa toàn bộ các vòng và những cạnh tuy vậy song

Xóa toàn bộ các vòng và những cạnh tuy vậy song trường đoản cú độ thị ban đầu.

*

Trong ngôi trường hợp những cạnh tuy nhiên song, giữ những cạnh tất cả trọng số nhỏ nhất và xóa cạnh còn lại.

*

Bước 2: chuẩn bị xếp tất cả các cạnh theo trọng số tăng nhiều

Bước tiếp sau là sinh sản một tập những cạnh cùng trọng số và sắp xếp chúng theo máy tự tăng dần đều về trọng số. (Giá trị trọng số là số hiển thị ở bên cạnh các cạnh vào hình minh họa trên.)

*

Bước 3: thêm 1 cạnh có trọng số tốt nhất

Bây giờ bọn chúng ta bắt đầu thêm những cạnh vào vật thị ban đầu từ cạnh tất cả trọng số rẻ nhất. Tại bất kể thời điểm nào, chúng ta cũng bắt buộc kiểm tra những thuộc tính của cây khung bao gồm còn được bảo trì hay không. Trong trường thích hợp khi thêm một cạnh nhưng làm phá vỡ thuộc tính của cây khung, thì bọn họ cần để ý đến việc ko thêm cạnh đó vào thứ thị.

*

Trọng số nhỏ nhất vào hình là 2 cùng đó là các cạnh là BD với DT, vị đó bọn họ thêm nhị cạnh này vào. Việc thêm nhì cạnh này không vi phạm luật các điểm sáng của cây khung do đó chúng ta có thể tiếp tục chọn lọc cạnh tiếp theo.

Trọng số tiếp theo sau là 3 với đó là các cạnh AC và CD. Bởi vì đó bọn họ thêm nhì cạnh này.

*

Trọng số tiếp theo sau trong hình là 4 và bọn họ thấy rằng khi thêm nó vào đồ thị sẽ khiến cho một quy trình trong đồ thị. Như hình minh họa:

*

Do đó họ bỏ qua trọng số này. Tiến trình của họ sẽ vứt qua/tránh vấn đề thêm các cạnh nhưng mà khi thêm cạnh đó vào sẽ tạo cho một chu trình trong trang bị thị.

*

Tiếp theo với nhị trọng số 5 và 6, chúng ta cũng thấy rằng chúng cũng khiến cho một chu trình. Vì đó họ bỏ qua nhì trọng số này và gửi tới trọng số tiếp theo.

*

Bây giờ đồ thị của bọn họ chỉ còn một nút nhằm thêm vào. Thân hai cạnh có trọng chu kỳ lượt là 7 cùng 8, họ thêm cạnh tất cả trọng số nhỏ hơn.

*

Bằng việc thêm cạnh SA, chúng ta đã có một cây khung nhỏ dại nhất theo giải thuật của Kruskal.


Đã có tiện ích Viet
Jack trên năng lượng điện thoại, giải bài tập SGK, SBT biên soạn văn, Văn mẫu, Thi online, bài xích giảng....miễn phí. Download ngay ứng dụng trên app android và i
OS.

Xem thêm: Top 10 Cách Khiêu Khích Đàn Ông Cực Thích, 6 Cách Khiêu Khích Chàng Dễ Ợt, Đàn Ông Cực Thích


*

*

Follow fanpage facebook của team https://www.facebook.com/hra.edu.vnteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.hra.edu.vn để thường xuyên theo dõi những loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile.... Mới nhất của chúng tôi.