南京网站开发询南京乐识wordpress 亲子博客

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

南京网站开发询南京乐识,wordpress 亲子博客,国际外贸平台排名,可做免费推广产品的网站有哪些图的相关算法 1. 图的遍历算法1.1 深度优先搜索1.2 广度优先搜索 2. 最小生成树求解算法普里姆(Prim)算法克鲁斯卡尔(Kruskal)算法 3. 拓扑排序4. 最短路径算法 1. 图的遍历算法 图的遍历是指从某个顶点出发#xff0c;沿着某条搜索路径对图中的所有顶点进行访问且只访问次的… 图的相关算法 1. 图的遍历算法1.1 深度优先搜索1.2 广度优先搜索 2. 最小生成树求解算法普里姆(Prim)算法克鲁斯卡尔(Kruskal)算法 3. 拓扑排序4. 最短路径算法 1. 图的遍历算法 图的遍历是指从某个顶点出发沿着某条搜索路径对图中的所有顶点进行访问且只访问次的过程。 图的遍历算法是求解图的连通性问题、拓扑排序及求关键路径等算法的基础。 图的遍历要比树的遍历复杂得多。因为图的任一个结点都可能与其余顶点相邻接所以在访问了某个顶点之后可能沿着某路径又回到该结点上为了避免对顶点进行重复访问在图的遍历过程中必须记下每个已访问过的顶点。深度优先搜索和广度优先搜索是两种遍历图的基本方法。 1.1 深度优先搜索 类似树的先根遍历在第一次经过一个顶点时就进行访问操作。遍历步骤如下 设置搜索指针 p使p指向顶点。访问p所指顶点并使p指向与其相邻接的且尚未被访问过的顶点。若p所指顶点存在则重复步骤(2)否则执行步骤(4)。沿着刚才访问的次序和方向回溯到一个尚有邻接顶点且未被访问过的顶点并使p指向这个未被访问的顶点然后重复步骤(2)直到所有的顶点均被访问为止。 int visited[MaxN] {0}; //调佣遍历算法前设置所有的顶点都被访问过 void Dfs(Graph G, int i) {EdgeNode *t; int j;printf(%d,i); //访问序号为i的顶点visited[i] 1; //序号为i的顶点已被访问过t G.Vertices[i].firstarc; //取顶点i的第一个邻接顶点while(t!NULL){ //检查所有与顶点i相邻接的顶点jt-adjvex; //顶点j为顶点i的一个邻接顶点if(visited[j]0) //若顶点j未被访问则从顶点j出发进行深度优先搜索Dfs(G,j);tt-nextarc; //取顶点i的下一个邻接顶点} }1.2 广度优先搜索 图广度优先搜索 图的广度优先搜索方法为:从图中的某个顶点v出发在访问了之后依次访问v的各个未被访问过的邻接点然后分别从这些邻接点出发依次访问它们的邻接点并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问直到图中所有已被访问的顶点的邻接点都被访问到。若此时还有未被访问的顶点则另选图中的一个未被访问的顶点作为起点重复上述过程直到图中所有的顶点都被访问到为止。 广度优先遍历图的特点是尽可能先进行横向搜索即最先访问的顶点的邻接点也先被访问。为此引入队列来保存已访问过的顶点序列即每当一个顶点被访问后就将其放入队列中当队头顶点出队时就访问其未被访问的邻接点并令这些邻接顶点入队。 void Bfs(Graph G) {EdgeNode *t; int i,j,k;int visited[MaxN]{0}; //调用遍历算法前设置所有的顶点都没有被访问过initQueue(Q); //创建一个空队列for(i0;iG.Vnum;i){if(!visited[i]){ //顶点i未被访问过enQueue(Q,i);printf(%d,i);visited[i]1; //访问顶点i并设置已访问标志while(!isEmpty(Q)){ //若队列不空则继续取顶点进行广度优先搜索deQueue(Q,k);tG.Vertices[k].firstarc;for(;t;tt-nextarc){ //检查所有与顶点K相邻接的顶点jt-adjvex; //顶点j是顶点k的一个邻接顶点if(visited[j]0){ //若顶点j未被访问过将j加入队列enQUeue(Q,j);printf(%d,j); //访问序号为j的顶点并设置已访问标志visited[j]1;}}}}} }2. 最小生成树求解算法 生成树设图GVE是个连通图如果其子图是一棵包含G的所有顶点的树则该子图称为G的生成树。 对于有n个顶点的连通图至少有 n-1 条边而生成树中恰好有 n-1条边所以连通图的生成树是该图的极小连通子图。若在图的生成树中任意加一条边则必然形成回路。 图的生成树不是唯一的。对于非连通图而言每个联通分量中的顶点集和遍历时走过的边集一起构成若干棵生成树把它们称为非连通图的生成树森林。 最小生成树对于连通网来说边是带权值的生成树的各边也带权值于是就把生成树各边的权值总和称为生成树的权,把权值最小的生成树称为最小生成树。求解最小生成树有许多实际的应用。普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法是两种常用的求解最小生成树算法。 普里姆(Prim)算法 克鲁斯卡尔(Kruskal)算法 3. 拓扑排序 在工程领域一个大的工程项目通常被划分为许多较小的子工程(称为活动)当这些子工程都完成时整个工程也就完成了。若以顶点表示活动用有向边表示活动之间的优先关系,则称这样的有向图为以顶点表示活动的网(Activity On Vertex network,AOV 网)。在有向网中若从顶点 v i v_i vi​到顶点 v j v_j vj​有一条有向路径则顶点 v i v_i vi​是 v j v_j vj​的前驱顶点 v j v_j vj​是 v i v_i vi​的后继。若 v i , v j v_i,v_j vi​,vj​是网中的一条弧则顶点 v i v_i vi​是 v j v_j vj​的直接前驱顶点 v j v_j vj​是 v i v_i vi​的直接后继。AOV 网中的弧表示了活动之间的优先关系也可以说是一种活动进行时的制约关系。 在 AOV 网中不应出现有向环、回路若存在的话则意味着某项活动必须以自身任务的完成为先决条件显然这是荒谬的。因此若要检测一个工程划分后是否可行首先就应检查对应的AOV 网是否存在回路。检测的方法是对其 AOV 网进行拓扑排序。 对一个有向图进行拓扑排序的结果会有两种情况 一种是所有顶点已输出此时整个拓扑排序完成说明网中不存在回路;另一种是尚有未输出的顶点剩余的顶点均有前驱顶点表明网中存在回路拓扑排序无法进行下去。

1. 最短路径算法 狄克斯特拉算法