在百度怎么做网站,jfinal网站开发,服装公司 网站怎么做,18款禁用黄a免费文章目录 回顾提要连通图生成树最小生成树构造最小生成树的算法普里姆(Prim)算法克鲁斯卡尔(Kruskal)算法 最短路径狄杰斯特拉 (Dijkstra) 算法当前最短路径的更新拓扑排序拓扑排序方法拓扑排序示例总结 回顾
图的遍历方法#xff1a;
深度优先遍历 (DFS)#xff1a;从任意… 文章目录 回顾提要连通图生成树最小生成树构造最小生成树的算法普里姆(Prim)算法克鲁斯卡尔(Kruskal)算法 最短路径狄杰斯特拉 (Dijkstra) 算法当前最短路径的更新拓扑排序拓扑排序方法拓扑排序示例总结 回顾
图的遍历方法
深度优先遍历 (DFS)从任意顶点开始访问其未访问过的邻接点直至全部访问完毕。广度优先遍历 (BFS)从任意顶点开始访问其所有未访问过的邻接点然后是下一层的邻接点直至所有顶点被访问。
提要
最小生成树的概念。最小生成树的构造算法 普里姆 (Prim) 算法克鲁斯卡尔 (Kruskal) 算法 单源点最短路径。拓扑排序。
连通图
连通图图中任意两个顶点都是连通的。在连通图中从任意顶点出发进行深度优先遍历或广度优先遍历都可以访问图中所有其他顶点。
生成树
生成树包含连通图全部顶点的极小连通子图即以最少的边连接连通图中所有的顶点。
最小生成树
最小生成树带权连通图的所有生成树中权值之和最小的生成树。在实际问题中如管道铺设问题可以应用最小生成树来最小化成本。 最小生成树带权连通图的所有生成树中权值之和最小的生成树。 在实际问题中的应用管道的铺设问题。 n 个小区只需铺设 n-1 条管线就能连通各条管线的投资成本不同如何使得总的投资成本最低最小生成树。
构造最小生成树的算法
普里姆 (Prim) 算法从任一顶点开始逐步扩展最小生成树每次添加权值最小的边。克鲁斯卡尔 (Kruskal) 算法按边权值从小到大的顺序选择边形成最小生成树不形成环。
普里姆(Prim)算法 示例 求解过程
初始化U{v}。v到其他顶点的所有边为候选边重复以下步骤n-1次使得其他n-1个顶点被加入到U中 从候选边中挑选权值最小的边输出设该边在V-U中的顶点是k将k加入U中考察当前V-U中的所有顶点j修改候选边若 (k, j) 的权值小于原来和顶点 j 关联的候选边则用 (k, j) 取代后者作为候选边。
克鲁斯卡尔(Kruskal)算法
假设N(V,E)是连通网(带权的图)令最小生成树的初始状态为包含全部n个顶点但没有边的非连通图T(V,{ })图中每个顶点自成一个连通分量。 在E中选择权值最小的边若该边依附的顶点落在T中不同的连通分量上则将此边加入到T中否则舍去此边而选择下一条权值最小的边。依此类推直至所有顶点都在同一连通分量上为止。
示例
求解过程
T的初始状态包含n个顶点、不包含边的森林T(VØ )按权值递增的顺序选择E中的n-1条安全边(uv)并加入T安全边指两个顶点分别是森林T里两棵树中的顶点的边。安全边的加入不会形成环。加入安全边可将森林中的两棵树连接成一棵更大的树。
最短路径
最短路径带权图中从源点到终点的所有路径中所经过边的权值之和最小的路径。 图的最短路径 单源点最短路径从一个顶点到其余各顶点的最短路径 每对顶点间的最短路径。
狄杰斯特拉 (Dijkstra) 算法
求解单源点最短路径的算法通过不断更新顶点间的最短路径来实现。
当前最短路径的更新 拓扑排序
拓扑排序在一个有向图中找一个满足所有有向边的方向的顶点序列的过程。
拓扑排序方法
从有向图中选择一个没有前驱入度为0的顶点并输出。从图中删去该顶点及发出的全部有向边。重复以上步骤直到所有顶点都被输出。
拓扑排序示例
计算机专业课程学习顺序的拓扑排序展示了如何根据先修课程的要求进行排序。 课程之间的先后关系可用有向图表示 拓扑序列C2-C7-C1-C3-C4-C5-C6 或C1-C2-C3-C4-C5-C7-C6 等 注意拓扑序列不一定唯一。
总结
普里姆 (Prim) 算法和克鲁斯卡尔 (Kruskal) 算法构造最小生成树的方法。狄杰斯特拉 (Dijkstra) 算法求解单源点最短路径。拓扑排序的应用。
