网站建设价格最低多少钱,小红书seo优化,企业网站建设管理系统,计算机 网站开发 文章prim是设置一个初始结点#xff0c;寻找其周围最小的边权值#xff0c;并将该结点作为初始结点#xff0c;继续寻找现在结点周围的边权值的最小值#xff0c;但要注意如果这次寻找的某个边权值没有上次的小的话仍然保留上一次的边权值#xff0c;即lowcast的值将会不变。 …prim是设置一个初始结点寻找其周围最小的边权值并将该结点作为初始结点继续寻找现在结点周围的边权值的最小值但要注意如果这次寻找的某个边权值没有上次的小的话仍然保留上一次的边权值即lowcast的值将会不变。 1 #includestdio.h2 #includeiostream3 #includestring.h4 #includealgorithm5 using namespace std;6 const int inf0x3f3f3f3f;///当两个点之间没有边时设置这两个边之间的距离为无穷大7 const int maxn110;///数组的长度8 int ma[maxn][maxn],lowcost[maxn];///ma[i][j]数组的用于存储i,j两点之间的距离lowcast[j]用于存储从标记边k到边j的边的长度9 bool vis[maxn];///用于记录点是否已经加入到树中
10 int nodenum,sum;
11 void prim()
12 {
13 int temp,k;
14 sum0;
15 memset(vis,false,sizeof(vis));
16 vis[1]true;///从1开始查询
17 for(int i1;inodenum;i)
18 {
19 lowcost[i]ma[1][i];
20
21 }
22 for(int i1;inodenum;i){
23 tempinf;///temp用于存储最短的距离
24 for(int j1;jnodenum;j){
25 if(!vis[j]templowcost[j])
26 templowcost[kj];///在赋值的同时把j的值赋给k下次就从k开始向其他结点寻找
27 if(tempinf)break;///如果temp值没有改变的话就证明该点不与其它点连通最小生成树建立失败跳出循环
28 vis[k]true;
29 sumtemp;
30 for(int j1;jnodenum;j){
31 if(!vis[j]lowcost[j]ma[k][j])///此时lowcast中其实还含有上一个结点到j的距离若ma[k][j]不足够小的话lowcast的值将不变
32 lowcost[j]ma[k][j];
33 }
34 }
35 }
36
37 }
38 int main()
39 {
40 int a,b,cost,edgenum;
41 while(cinnodenumnodenum){
42 memset(ma,inf,sizeof(ma));///初始化最开始所有的点之间都不关联
43 edgenumnodenum*(nodenum-1)/2;///edgenum是所有点之间都有边相连的边的个数
44 for(int i1;iedgenum;i){
45 cinabcost;
46 if(costma[a][b]){
47 ma[a][b]ma[b][a]cost;///无向图的边没有方向
48 }
49 }
50 prim();
51 coutsumendl;
52 }
53 } View Code 转载于:https://www.cnblogs.com/shangjindexiaoqingnian/p/5846665.html
