当前位置: 首页 > news >正文

佛山网站建设推广订做sem竞价培训

佛山网站建设推广订做,sem竞价培训,广州网站制作到诺然,网站建设岗位风险防控引子: 无向图如果是一个网,那么它的所有的生成树中必有一颗生成树的边的权值之和是最小的,我们称 这颗权值和最小的树为:“最小生成树”(MST)。 其中,一棵树的代价就是树中所有权值之和。 而…

引子:

无向图如果是一个网,那么它的所有的生成树中必有一颗生成树的边的权值之和是最小的,我们称

这颗权值和最小的树为:“最小生成树”(MST)。

其中,一棵树的代价就是树中所有权值之和。

而在现实中,最小生成树的概念可以用来解决很多实际问题,例如,在n个城市之间建立交通网,

那么哪一条路径是最短的呢?就可以用最小生成树来解决。

算法思想:

设G = (V,E)为以连通网,其中V为顶点集合,E为带权边集合。

设置两个新集合U和T:

U用于存放最小生成树的顶点,T用于存放最小生成树的边。

令集合的初值为:{u0}(假设构造最小生成树时,从顶点u0出发。)

集合T的初值为{}。

从所有u∈U,v∈V-U的边(u,v)中,选取最小权值的边(u0,v0),将顶点v0加入集合U中,将边

(u0,v0)加入集合T中。

如此不断重复,知道U = V,最小生成树构造完成,集合T中包含了最小生成树中的所有边。

分析算法可知:

为了实现Prim算法,需要一个辅助数组closedge以记录从U到V-U具有最小代价的边。

对于closedge数组需要包含两个域:

adjvex和lowcost,其中lowcost = 0表示若顶点v不在生成树上,用closedge.lowcost存放v与生成树

上的另一个顶点的序号所构成边的权值。

adjvex存放与该边相关联的生成树上的另一顶点的序号。

算法生成图

对于下面这个无向图例子来说:

                                                                                                                                                                                                 

算法的执行过程如下:

代码部分:

#include<stdio.h>
#define MAX 100
typedef struct Mgraph{char vertex[MAX];int arcs[MAX][MAX];int vexnum,arcnum;
}Mgraph;typedef struct Closedge{char adjvex[MAX];int lowcost[MAX];
}Closedge;int LocateVerTex(Mgraph *G,char v)
{int k;for(k=0;k<G->vexnum;k++)if(G->vertex[k] == v)return k;return -1;
}void CreateMgraph(Mgraph *G)
{int i,j,weight,adj1,adj2;char v1,v2;printf("请输入顶点数和边数:\n");scanf("%d %d",&G->vexnum,&G->arcnum);getchar();printf("请输入:{%d}个顶点:\n",G->vexnum);for(i=0;i<G->vexnum;i++)scanf("%c",&G->vertex[i]);getchar();printf("请输入:{%d}条边:(格式如下:v1 v2 权值).\n",G->arcnum);for(i=0;i<G->vexnum;i++){for(j=0;j<G->vexnum;j++){G->arcs[i][j] = 9999;}}for(i=0;i<G->arcnum;i++){scanf("%c %c %d",&v1,&v2,&weight);getchar();adj1 = LocateVerTex(G,v1);adj2 = LocateVerTex(G,v2);if(adj1 == -1 || adj2 == -1){printf("失败.\n");i = i - 1;continue;}else{G->arcs[adj1][adj2] = weight;G->arcs[adj2][adj1] = weight;printf("成功.\n");}}
}int MiniNum(Closedge *closedge,Mgraph *G)
{int j,p = 1,min = 999;for(j=0;j<G->vexnum;j++){if(closedge->lowcost[j] != 0 && closedge->lowcost[j] < min){min = closedge->lowcost[j];p = j;}}return p;
}void MiniTree_Prim(Mgraph *G,char u)
{int i,j,k,num;k = LocateVerTex(G,u);Closedge closedge;for(i=0;i<G->vexnum;i++){if(i!=k){closedge.adjvex[i] = u;closedge.lowcost[i] = G->arcs[k][i];}}closedge.lowcost[k] = 0;printf("最小生成树的各条边为:\n");for(i=1;i<G->vexnum;i++){k = MiniNum(&closedge,G);printf("边:<%c,%c>,权值为{%d}:\n",closedge.adjvex[k],G->vertex[k],closedge.lowcost[k]);closedge.lowcost[k] = 0;for(j=0;j<G->vexnum;j++){if(G->arcs[k][j] < closedge.lowcost[j]){closedge.adjvex[j] = G->vertex[k];closedge.lowcost[j] = G->arcs[k][j];}}}
}int main()
{Mgraph G;CreateMgraph(&G);MiniTree_Prim(&G,'A');return 0;
}

验证部分:

http://www.hrbkazy.com/news/22668.html

相关文章:

  • 杭州网站制作报价域名注册平台有哪些
  • 塑胶原料东莞网站建设技术支持项目宣传推广方案
  • c 可以做哪些网站泰州百度seo公司
  • 厦门做百度推广的网站泉州百度seo公司
  • p2p的网站开发郑州整站网站优化
  • 增城网站建设公司百度搜索关键词热度
  • 打不开网页是怎么回事成都网站改版优化
  • python电商网站开发网站seo哪家好
  • 肇庆网站建设推广长沙网站优化体验
  • 大连建设项目优化方案的格式及范文
  • 国开机考网站界面设计宁波网络优化seo
  • 银川网站建设怎么样北京seo招聘信息
  • 网站结构与导航设计网络营销推广有哪些方法
  • 新疆建设兵团门户网站竞价代运营
  • 做网站销售好吗企业网站注册
  • 岳阳做网站seo网络营销技术
  • 寄生虫网站排名代做长沙官网seo分析
  • jsp与网站开发期末试题广东东莞最新疫情
  • 百度收录网站方法软文兼职
  • 厦门网站排名优化费用抖音黑科技引流推广神器
  • bootstrap网站案例优化大师免费下载
  • 盈润企业网站管理系统如何进行网站推广
  • 建设银行造价咨询中心网站线上推广网络公司
  • 网站后台怎么修改文字lol今日赛事直播
  • 网站制作的公司搜索引擎营销的实现方法有哪些
  • 一个网站的建设需要哪些流程最近一周新闻热点回顾
  • 徐州手机网站制作刷外链
  • pc网站手机版开发电商还有发展前景吗
  • 为什么WORDPRESS后台很卡网站优化快速排名软件
  • 做网站在哪里可以找到高清壁纸指数分布的分布函数