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++)

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. [crayon-5f07fbc110555848583383/] 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. [crayon-5f07fbc11055f442250102/] 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ú…

User Rating: 2.85 ( 2 votes)

About ngoton

Ngô Tôn is a programmer with passion for tailored software solutions. Comes with 6+ 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ị

1.     Tóm tắt một số khái niệm Đồ thị là một thể hiện bao gồm …

Leave a Reply

Your email address will not be published. Required fields are marked *