电商网站设计图,甘肃业聚质网络科技有限公司,动漫网站开发研究内容,北京信息网招聘最新一、图的相关算法1、图的分类知识如下图#xff1a;2、生成树概念对连通图进行遍历#xff0c;过程中所经过的边和顶点的组合可看做是一棵普通树#xff0c;通常称为生成树。连通图的生成树具有这样的特征#xff1a;边的数量 顶点数 - 13、最小生成树在连通网的所有生成树… 一、图的相关算法1、图的分类知识如下图 2、生成树概念对连通图进行遍历过程中所经过的边和顶点的组合可看做是一棵普通树通常称为生成树。连通图的生成树具有这样的特征边的数量 顶点数 - 13、最小生成树在连通网的所有生成树中所有边的代价和权值最小的生成树称为最小生成树。 4、 最小生成树的算法4.1普里姆算法(Prim算法)它是图论中的一种算法可在加权连通图里搜索最小生成树。即由此算法搜索到的边子集所构成的树中不但包括了连通图里的所有顶点且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克英语Vojtěch Jarník发现并在1957年由美国计算机科学家罗伯特·普里姆Robert C. Prim独立发现1959年艾兹格·迪科斯彻再次发现了该算法。因此在某些场合普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆亚尔尼克算法。算法如下void prim(MGraph g,int v){ int lowcost[MAXV],min,ng.vexnum; int closest[MAXV],i,j,k; for (i0;in;i) //给lowcost[]和closest[]置初始值 { lowcost[i]g.edges[v][i]; closest[i]v; } for (i1;in;i) //找出n-1个顶点 { minINF; for (j0;jn;j) //在(V-U)中找出离U最近的顶点k if (lowcost[j]!0 lowcost[j]min) { minlowcost[j];kj; } printf( 边(%d,%d)权为:%d\n,closest[k],k,min); lowcost[k]0; //标记k已经加入U for (j0;jn;j) //修改数组lowcost和closest if (g.edges[k][j]!0 g.edges[k][j]lowcost[j]) { lowcost[j]g.edges[k][j];closest[j]k; } }}算法过程 4.2 克鲁斯卡尔Kruskal算法1、概念该算法可以称为“加边法”初始最小生成树边数为0每迭代一次就选择一条满足条件的最小代价边加入到最小生成树的边集合里。2、算法步骤1. 把图中的所有边按代价从小到大进行排序2. 把图中的n个顶点看成独立的n棵树组成的森林3. 按权值从小到大选择边所选的边连接的两个顶点,应属于两颗不同的树则成为最小生成树的一条边并将这两颗树合并作为一颗树。4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。3、算法过程 5、最小生成树算法的应用比如要在n个城市之间铺设光缆主要目标是要使这 n 个城市的任意两个之间都可以通信因为铺设光缆的费用很高且各个城市之间铺设光缆的费用不同因此另一个目标是要使铺设光缆的总费用最低。这个时候需要找到带权的最小生成树来解决这个问题。 二、拓扑排序1、定义由某个集合上的一个偏序得到该集合上的一个全序这个操作称之为拓扑排序。2、AOV网在工程领域一个大的工程通常会被划分为许多较少的子工程当子工程都完成了那么整个大工程也就完成了。若以顶点表示活动用有向边表示子工程之间的优先关系。这样的有向图以顶点表示活动的网就是AOV网。AOV网表示了子工程之间的优先关系也是活动进行时的制约关系。3、拓扑排序拓扑排序是将AOV网中所有的顶点排成一个线性序列的过程。并且满足若在AOV网中从顶点A到B有一条路径那么A比然在B之前。4、执行步骤(1) 选择一个入度为0的顶点并输出之(2) 从网中删除此顶点及所有出边。循环结束后若输出的顶点数小于网中的顶点数则输出“有回路”信息否则输出的顶点序列就是一种拓扑序列。 IT技术分享社区个人博客网站https://programmerblog.xyz文章推荐程序员效率画流程图常用的工具程序员效率整理常用的在线笔记软件远程办公常用的远程协助软件你都知道吗51单片机程序下载、ISP及串口基础知识硬件断路器、接触器、继电器基础知识
