tailieunhanh - Giáo trình hình thành hệ thống ứng dụng nguyên lý điều khiển luồng theo tiến trình biểu diễn số p6

Tham khảo tài liệu 'giáo trình hình thành hệ thống ứng dụng nguyên lý điều khiển luồng theo tiến trình biểu diễn số p6', công nghệ thông tin, tin học văn phòng phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Thuật toán Prim dựa trên những định lý sau đây Định lý . Một cây là một MST nếu và chỉ nếu cây đó chứa cạnh ngắn nhất trong mọi cutset chia các nút thành hai thành phần. Để thực hiện thuật toán Prim cần phải theo dõi khoảng cách từ mỗi nút không thuộc cây tới cây và cập nhật khoảng cách đó mỗi khi có một nút được thêm vào cây. Việc đó được thực hiện dễ dàng đơn giản chỉ là duy trì một dãy d_tree có các thông tin về khoảng cách đã nói ở trên. Quá trình đó tuân theo array n - Prim n root dist dcl dist n n pred n d_tree n in tree n index - FindMin d_min - INFINITY for each i n if in_tree j and d_tree i d min i min - i d min - d tree i return i min void -Scan i for each j n if in_tree j and d_tree j dist i j d_tree j - dist i j pred j -i d_tree - INFINITY pred - -1 in_tree - FALSE d_tree root -0 in tree -0 while in tree n i - FindMin in_tree i - TRUE Scan i _in_tree _in_tree 1 return pred FindMin trả về một nút không thuộc cây và gần cây nhất. Scan cập nhật khoảng cách tới cây đối với các nút không thuộc cây. 57 Có thể thấy rằng độ phức tạp của thuật toán này là O n2 cả hai hàm FindMin và Scan có độ phức tạp là O n và mỗi hàm được thực hiện n lần. So sánh với thuật toán Kruskal ta thấy rằng độ phức tạp của thuật toán Prim tăng nhanh hơn so với độ phức tạp của thuật toán Kruskal nếu m số lượng các cạnh bằng O n2 còn nếu m có cùng bậc với n thì độ phức tạp của thuật toán Kruskal tăng nhanh hơn. Có thể tăng tốc thuật toán Prim trong trường hợp graph là một graph mỏng bằng cách chỉ quan tâm đến các nút láng giềng của nút i vừa được thêm vào cây. Nếu sẵn có các thông tin kề liền vòng lặp for trong Scan có thể trở thành. for each j n_adj_list i Độ phức tạp của Scan trở thành O d với d là bậc của nút i. Chính vì thế độ phức tạp tổng cộng của Scan giảm từ O n2 xuống O m . Thiết lập một tập kề liền cho toàn bộ một graph là một phép toán có độ phức tạp bằng O m index nn list - SetAdj n m ends dcl ends m 2 n adj list n list for node 1 to n n adj list node - 0 for edge 1 to m .