网站怎么通过流量赚钱,软件技术就业方向,做民族网站的配色哪些颜色适合,快速网站排名提升一、图的遍历
从图中的某个顶点出发#xff0c;沿着某条搜索路径对图中的所有顶点进行访问#xff0c;且#xff0c;只访问一次的过程。
图的遍历比树的遍历复杂#xff0c;因为要避免对顶点进行重复访问#xff0c;所以在图的遍历过程中#xff0c;必须记下每个已访问…一、图的遍历
从图中的某个顶点出发沿着某条搜索路径对图中的所有顶点进行访问且只访问一次的过程。
图的遍历比树的遍历复杂因为要避免对顶点进行重复访问所以在图的遍历过程中必须记下每个已访问过的顶点。 树的遍历 先序遍历中序遍历后序遍历层次遍历 图的遍历基本方法
深度优先搜索广度优先搜索 1-1、深度优先搜索DFS
示例 深度遍历涉及到回溯这是递归的思想。 时间复杂度 深度优先遍历图的过程实质上是对某个顶点查找其邻接点的过程其耗费的时间取决于所采用的存储结构。 图中的顶点数n图中的边数e 1当图用邻接矩阵表示时查找所有顶点的邻接点所需时间为 O(n^2)。 2若以邻接表作为图的存储结构则需要 O(e)的时间复杂度查找所有顶点的邻接点。因此当以邻接表作为存储结构时深度优先搜索遍历图的时间复杂度为 O(n e)。 1-2、广度优先搜索BFS 将队头的元素和其所有的相邻节点入队列。 时间复杂度 遍历图的过程实质上是通过边找邻接点的过程因此广度优先搜索遍历图和深度优先搜索遍历图的运算时间复杂度相同。不同之处仅仅在于对定点的访问次序不同。 1-3、真题
真题1 真题2 真题3 G中任意两个顶点之间均有边存在——完全图 无向连通图 从图中任意顶点出发可遍历图中所有顶点 有向连通图 从图中任意顶点出发可遍历图中所有顶点 真题4 真题5B、A 强连通图从图中任意顶点出发能够遍历图中所有节点。因为V5没有任何出度所以不能从V5开始遍历所以不是强连通图。 真题6 二、拓扑排序
2-1、AOV网有向无环图
有向图以顶点表示活动以有向边表示活动之间的优先关系也是活动之间的制约关系。
在AOV网中不应该出现有向环。 2-2、拓扑排序
AOV网代表一个工程计划AOV网的拓扑排序就是一个工程顺利完成的可行方案。AOV网的拓扑排序方法如下
1、在AOV网中选择一个入度为0没有前驱的顶点输出它
2、从网中删除该顶点及与该顶点有关的所有弧
3、重复上下两步直到网中不存在入度为0的顶点为止。
示例 在AOV网的拓扑序列中顶点Vi在Vj之前则 可能存在弧Vi, Vj一定不存在弧Vj, ViVi——Vj 可能存在Vi到Vj的路径一定不存在Vj到Vi的路径。Vi——Vx——Vj 2-3、真题
真题1 真题2 真题3 真题4 真题5
