prim算法精讲prim思路1.寻找非生成树节点距离生成树最近的节点2.将距离生成树最近节点加入生成树3.更新所有非生成树节点到生成树的最短距离具体代码细节见代码注释#includeiostream #includevector #include climits using namespace std; int main(){ int n,m,s,t,val; cinnm; //为什么n1因为编号从1开始共n个所以需要开辟边长为n1的邻接矩阵 //为什么初始化为10001因为本题val最大值是10000后面涉及到要比较“连接到cur节点的权值”与“上一状态的到生成树最短距离”所以把没有连接的节点初始值赋值为一个大值防止通过if判断 vectorvectorint graph(n1,vectorint(n1,10001)); while(m--){ cinstval; //因为是无向图所以两边都要赋值 graph[s][t] val; graph[t][s] val; } //用来判断节点是否已经加入生成树初始都不在树中全为false vectorbool isIntree(n1,false); //用来记录每个节点到生成树的最短距离因为要记录最小值所以初始化为最大值 vectorint minDist(n1,INT_MAX); //因为连接n个节点只需n-1条边所以循环n-1次就好了按照prim算法逻辑每循环一次就是加一条边 for(int i1;in;i){ //----------寻找非生成树节点距离生成树最近的节点---------- //一开始没有节点在树中所以先赋值一个cur1应对第一次循环的情况 int cur 1; //用来记录“最近”这个最小值 int minval INT_MAX; //遍历minDist中的节点寻找最小值 for(int j1;jn;j){ //节点不能已经在树中并且当所记录的距离生成树的最短记录小于当前最小值时就更新最小值然后把当前节点编号赋值给cur遍历完minDist数组就找到最小值编号了也就是非生成树节点距离生成树最近的节点 if(isIntree[j]false minvalminDist[j]){ minval minDist[j]; cur j; } } //----------将距离生成树最近节点加入生成树---------- //其实就是把cur位置的isIntree置为true isIntree[cur] true; //----------更新minDist数组---------- for(int k1;kn;k){ //因为生成树加入了新的节点所以可能非生成树节点距离生成树的节点有变化需要进行更新 //当节点不在树中并且与新节点cur连接不是初始化值10001且距离小于之前记录的到生成树最短距离就把最短距离更新为新的距离 if(isIntree[k]false graph[cur][k]minDist[k]){ //minDist[k]为之前记录的到生成树最短距离graph[cur][k]为与新节点cur连接的距离k节点与cur连接 minDist[k] graph[cur][k]; } } } int result 0; //此时所有节点都已经加入了生成树连接在一起minDist记录了每个节点加入生成树时所使用的距离值所以只需累加minDist数组即可。由于节点1一开始没有赋距离值就自己加入生成树了所以节点1的值不计入从2开始。 for(int i2;in;i) resultminDist[i]; coutresultendl; }kruskal算法精讲