prim贪心算法java 复杂度

Prim贪婪算法，也称为Prim-Jarnik算法或最小生成树算法，是一个用于求解图中最小生成树（Minimum Spanning Tree, MST）的经典算法。在Java中，我们可以使用邻接矩阵或邻接表数据结构来实现。

**基本思路**：
- 从某个顶点开始，选择与其相连且未被选中的边中权重最小的一条边加入到已选边集合中。
- 重复此过程，每次增加一条边，直到所有顶点都被连接起来形成一棵树，且总权重是最小的。

**Java代码示例**（使用邻接矩阵）：

public class Prim {
    private int V; // 图的顶点数
    private int[][] graph; // 邻接矩阵

    public Graph(int vertices) {
        this.V = vertices;
        graph = new int[vertices][vertices];
        // 填充图的邻接矩阵
    }

    // 添加边的方法
    public void addEdge(int v, int w) {
        graph[v][w] = graph[w][v] = w; // 如果v到w有边，设其权重为w
    }

    // 主函数，执行Prim算法
    public void primMST() {
        boolean[] visited = new boolean[V]; // 记录每个顶点是否被访问过
        int key[] = new int[V]; // 存储每步选取的边的权值
        int minKey = Integer.MAX_VALUE, u; // 最小键和其对应的顶点

        key[0] = 0; // 初始节点总是最小权重
        visited = true;

        for (int count = 0; count < V - 1; count++) {
            minKey = Integer.MAX_VALUE;
            for (int v = 0; v < V; v++)
                if (!visited[v] && graph[u][v] < minKey)
                    minKey = graph[u][v], u = v;

            visited[u] = true;
            // 将当前找到的最小边加入生成树
            // 更新key数组，记录新添加的边
        }
        // 输出生成树的信息
    }
}

**时间复杂度**：
Prim算法的时间复杂度为O(E log V)，其中E是边的数量，V是顶点数量。这是因为每次遍历都会对所有的边进行比较，而找到下一个最小值的操作可以通过优先队列等数据结构优化到O(log V)。