prim算法的实现.doc

Prim算法是一种用于寻找图中最小生成树的著名算法，由捷克数学家Vojtěch Jarník在1930年提出，并由美国计算机科学家Robert C. Prim在1957年独立发现。该算法的目标是从图的一个顶点开始，逐步添加边，直到构建出一个连接所有顶点的树，且总权重最小。 在上述代码中，Prim算法的实现步骤如下： 1. 初始化：定义了一个邻接矩阵`Matrix`来表示图的结构，其中`MAXVEVERTEXNUM`为图的顶点数量，`MAXIMUMCOST`表示两个不相邻顶点之间的距离，默认设置为100。函数`initadjmatrix`用于初始化这个矩阵，矩阵中的每个元素表示两个顶点之间的距离。 2. `initadjmatrix`函数还初始化了数组`truev`，它用于标记顶点是属于已经选择的最小生成树（V集合）还是待考虑的顶点集（S-V集合），初始时所有顶点都在S-V集合中，即`truev[i]=0`。 3. 找到最小边：`minimum`函数负责找出S-V集合中与V集合连接的边中权值最小的一条，并将其对应的顶点移动到V集合中。它通过遍历`temp1`和`temp2`数组，这两个数组分别存储了边的权重和对应顶点的下标，找到最小权重的边，并更新`truev`数组。 4. Prim算法核心：`prim`函数是Prim算法的主要实现，它使用一个循环来逐步构建最小生成树。在每次迭代中，`prim`函数会调用`minimum`函数找到当前最小的边，并将该边的终点加入到V集合中。当V集合的顶点数等于图的顶点总数减一（即所有顶点都被包含在最小生成树中）时，算法结束。 代码中使用了两个辅助数组`temp1`和`temp2`，它们在每次迭代中存储了V集合和S-V集合之间的边的权重和对应顶点的下标。`N`变量记录了当前存储的边的数量。 总体来说，这段代码实现了一个基于邻接矩阵的Prim算法，通过不断选择最小的边来构建最小生成树。尽管代码简洁，但理解Prim算法的核心思想和操作步骤对于学习图论和算法优化至关重要。在实际应用中，更高效的实现方式可能包括使用优先队列（如二叉堆）来快速找到最小权重的边，以减少算法的时间复杂度。