[NL1] Tìm đường đi ngắn nhất bằng giải thuật Prim [NL1] Tìm đường đi ngắn nhất bằng giải thuật Prim

Với một đồ thị liên thông, vô hướng cho trước, cây bao trùm của nó là một đồ thị con có dạng cây và có tất cả các đỉnh liên thông với nhau. Một đồ thị có thể có nhiều cây bao phủ khác nhau.
Chúng ta cũng có thể gán một trọng số cho mỗi cạnh, là con số biểu thị sự "không ưa thích" và dùng nó để tính toán trọng số của một cây bao trùm bằng cách cộng tất cả trọng số của cạnh trong cây bao trùm đó.
Khi đó, một cây bao trùm nhỏ nhất là một cây bao trùm có trọng số bé hơn bằng trọng số của tất cả các cây bao trùm khác. Tổng quát hơn, bất kỳ một đồ thị vô hướng (không nhất thiết liên thông) đều có một rừng bao phủ nhỏ nhất, là hội của các cây bao trùm nhỏ nhất của các thành phần liên thông của nó.


Thông tin chung về đề tài:
- Ngôn ngữ: C#
- Dung lượng: 84 KB
Download đề tài này[You must be registered and logged in to see this link.]