找到目前权值最小的点的编号存储minu
时间: 2023-04-09 19:00:27 浏览: 48
我可以回答这个问题。要找到目前权值最小的点的编号,可以使用Dijkstra算法或者Prim算法。在实现算法时,需要使用一个数组来存储每个点的权值,然后在遍历过程中更新这个数组,找到最小值。最后返回最小值对应的点的编号即可。
相关问题
void RudeGraph(MGraph *G,int b,int k){ //迪杰斯特拉求最短路径 int i,j,min,minu; min=1000; for(j=1;j<=G->v;j++){ if(G->arc[b][j]<5000&&G->vexs[b].quanzhi+G->arc[b][j]<G->vexs[j].quanzhi&&G->vexs[j].park==0){ G->vexs[j].prenum=b; //更新当前顶点的直接前驱节点 G->vexs[j].quanzhi=G->vexs[b].quanzhi+G->arc[b][j]; //对顶点的权值进行更新 } } G->vexs[b].park=1; for(i=1;i<=G->v;i++){ //找到目前权值最小的点的编号存储minu if(G->vexs[i].quanzhi<min&&i!=b&&G->vexs[i].park==0){ min=G->vexs[i].quanzhi; minu=i; } } k++; if(k<G->v) RudeGraph(G,minu,k); //对当前权值最小的点进行递归 else //有个记录前驱编号的还没用到,先求出最短路径再实现输出 return ; }是什么意思
这是一个使用迪杰斯特拉算法求解最短路径的函数。其中,MGraph是一个结构体,包含一个邻接矩阵和一个顶点数组,b表示起点编号,k表示递归深度。该函数会遍历所有与起点b相邻的顶点,更新它们的权值(即到起点的距离),并标记它们已经被访问过。然后,从未被标记过的顶点中选择权值最小的顶点minu,以它作为新的起点进行递归,直到所有顶点都被标记过或者递归深度达到了总顶点数。最后可以根据顶点数组中存储的前驱节点信息,输出起点到其他顶点的最短路径。
最小生成树的权值计算
最小生成树的权值计算可以通过以下步骤实现:
1. 初始化mark数组,用于标记顶点是否在生成树内,初始值为False。
2. 初始化min数组,用于存储顶点i到生成树相连的最小边权重,初始值为正无穷。
3. 初始化SUM变量,用于存储最小生成树的权值之和,初始值为0。
4. 选择一个起始顶点,将其标记为已访问,并将min数组中对应位置的值设为0。
5. 重复以下步骤,直到所有顶点都被加入生成树:
- 遍历所有未访问的顶点,找到与生成树距离最小的顶点,将其标记为已访问。
- 更新min数组中与新加入的顶点相连的顶点的最小边权重,如果找到更小的权重,则更新min数组中对应位置的值。
- 将新加入的顶点与生成树相连的边的权重加到SUM变量中。
6. 最终,SUM变量的值即为最小生成树的权值之和。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)