Hi, I am

Ngô Tôn

I am a programmer.

Home / HCMUS / Graph Theory / Tìm cây khung nhỏ nhất với Prim & Kruskal

Tìm cây khung nhỏ nhất với Prim & Kruskal

1.     Thuật toán Prim

Cho G=(X,E) là một đồ thị liên thông có trọng gồm n đỉnh. Thuật toán Prim được dùng để tìm ra cây khung NN của G.

Chú ý: trong các thuật toán tìm khung ngắn nhất chúng ta có thể bỏ đi hướng các cạnh và các khuyên; đối với cạnh song song thì có thể bỏ đi và chỉ để lại một cạnh trọng lượng nhỏ nhất trong chúng.

Chú ý: ta cũng cần xác định đồ thị đưa vào có liên thông hay không trước khi gọi hàm PrimAlg đồng thời chú ý đồ thị có hướng (xét cả hai chiều và lấy cạnh có trọng nhỏ nhất!!!quan trọng!!!).

2.    Thuật toán Kruskal

Cho G=(X,E) là một đồ thị liên thông có trọng gồm n đỉnh. Thuật toán Kruskal được dùng để tìm ra cây khung ngắn nhất của G.

Chú ý: trong các thuật toán tìm khung ngắn nhất chúng ta có thể bỏ đi hướng các cạnh và các khuyên; đối với cạnh song song thì có thể bỏ đi và chỉ để lại một cạnh trọng lượng nhỏ nhất trong chúng.

So sánh với Prim: Trong Prim, chúng ta thực hiện việc mở rộng tập đã xét (ban đầu chỉ gồm một đỉnh, 0 cạnh thành n đỉnh, n-1 cạnh) dựa trên các cạnh ngắn nhất nối giữa tập đã xét và tập chưa xét. Như vậy, có trường hợp một cạnh sẽ phải xét đi xét nhiều lần rồi mới được chọn, thậm chí không hề được chọn.

Đối với Kruskal, cũng thêm lần lượt các cạnh vào đồ thị, theo thứ tự từ trọng nhỏ nhất đến trọng lớn nhất (như vậy mỗi cạnh sẽ chỉ được duyệt một lần duy nhất). Ta chỉ bổ sung cạnh vào cây khung nếu việc thêm cạnh này không làm phát sinh ra chu trình.

Chú ý: ta cũng cần xác định đồ thị đưa vào có liên thông hay không đồng thời chú ý đồ thị có hướng (xét cả hai chiều và lấy cạnh có trọng nhỏ nhất!!!quan trọng!!!) trước khi gọi hàm KruskalAlg.

Source code (C++)

About ngoton

Ngô Tôn is a programmer with passion for tailored software solutions. Comes with 7+ years of IT experience, to execute beautiful front-end experiences with secure and robust back-end solutions.

Check Also

Biểu diễn và thao tác trên đồ thị

Mục lục 3.1.  Lưu trữ3.2.  Đọc và xuất đồ thị3.3.  Kiểm tra đồ thị không …

3
Leave a Reply

avatar
3 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
3 Comment authors
nguyen thanh dongtruc vanddfeeat Recent comment authors
  Subscribe  
newest oldest most voted
Notify of
ddfeeat
Guest

d

truc van
Guest
truc van

hello

nguyen thanh dong
Guest
nguyen thanh dong

thanks