Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.7 kB
2
Indexable
Never
Thuật toán Prim là một thuật toán tìm cây khung nhỏ nhất trong đồ thị. Nó bắt đầu từ một đỉnh bất kỳ và lựa chọn cạnh có trọng số nhỏ nhất để thêm vào cây khung. Sau đó, nó tiếp tục lựa chọn cạnh có trọng số nhỏ nhất kết nối với một đỉnh đã được thêm vào cây khung và một đỉnh chưa được thêm vào cây khung. Quá trình này được lặp lại cho đến khi tất cả các đỉnh đều được thêm vào cây khung.

Đây là một ví dụ về cách triển khai thuật toán Prim bằng Java:

```java
import java.util.Arrays;

public class Prim {
    public static int prim(int[][] graph) {
        int n = graph.length;
        int[] dist = new int[n];
        boolean[] visited = new boolean[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;
        int res = 0;
        for (int i = 0; i < n; i++) {
            int u = -1;
            for (int j = 0; j < n; j++) {
                if (!visited[j] && (u == -1 || dist[u] > dist[j])) {
                    u = j;
                }
            }
            if (i != 0 && dist[u] == Integer.MAX_VALUE) {
                return -1;
            }
            visited[u] = true;
            res += dist[u];
            for (int v = 0; v < n; v++) {
                if (!visited[v] && graph[u][v] != 0) {
                    dist[v] = Math.min(dist[v], graph[u][v]);
                }
            }
        }
        return res;
    }
}
```

Bạn có thể sử dụng mã này như một cơ sở để giải quyết bài toán của mình. Bạn có muốn biết thêm chi tiết gì không?