<p><strong>Giải thuật Prim (tìm cây khung cực tiểu)</strong></p><p><strong>Dữ liệu:</strong></p><ul><li>Đồ thị vô hướng có trọng số G=(V,E)G = (V, E)G=(V,E)</li><li>Đồ thị liên thông</li></ul><p><strong>Ý tưởng</strong></p><ul><li>Bắt đầu từ một đỉnh bất kỳ</li><li>Mỗi bước chọn <strong>cạnh có trọng số nhỏ nhất nối từ tập đã chọn ra ngoài</strong></li><li>Mở rộng dần thành cây</li></ul><p><strong>Giải thuật</strong></p><p>Bước 1:<br>   Chọn một đỉnh bắt đầu s</p><p>   Khởi tạo:<br>       Với mỗi đỉnh u:<br>           dist[u] = vô cùng<br>           parent[u] = -1</p><p>       dist[s] = 0</p><p>Bước 2:<br>   Tạo tập các đỉnh chưa chọn (ban đầu gồm tất cả các đỉnh)</p><p>Bước 3:<br>   Lặp cho đến khi tập chưa chọn rỗng:</p><p>       Chọn đỉnh u chưa chọn sao cho dist[u] nhỏ nhất</p><p>       Đưa u vào cây khung</p><p>       Với mỗi đỉnh v kề với u mà chưa được chọn:<br>           Nếu dist[v] > trọng số(u, v) thì:</p><p>               Cập nhật:<br>                   dist[v] = trọng số(u, v)<br>                   parent[v] = u</p><p>Bước 4:<br>   Sau khi kết thúc:<br>       Tập các cạnh (parent[v], v) tạo thành cây khung cực tiểu</p><p><i><strong>***Tổng trọng số = tổng dist[v] với mọi v ≠ s</strong></i></p><p> </p>