网站浮动窗口怎么做的,我家我设计,二次开发比一次开发难吗,wordpress中文企业主题 下载1 引言遍历是指从某个节点出发#xff0c;按照一定的的搜索路线#xff0c;依次访问对数据结构中的全部节点#xff0c;且每个节点仅访问一次。 在二叉树基础中#xff0c;介绍了对于树的遍历。树的遍历是指从根节点出发#xff0c;按照一定的访问规则#xff0c;依次… 1 引言 遍历是指从某个节点出发按照一定的的搜索路线依次访问对数据结构中的全部节点且每个节点仅访问一次。 在二叉树基础中介绍了对于树的遍历。树的遍历是指从根节点出发按照一定的访问规则依次访问树的每个节点信息。树的遍历过程根据访问规则的不同主要分为四种遍历方式 (1)先序遍历 (2)中序遍历 (3)后序遍历 (4)层次遍历 类似的图的遍历是指从给定图中任意指定的顶点(称为初始点)出发按照某种搜索方法沿着图的边访问图中的所有顶点使每个顶点仅被访问一次这个过程称为图的遍历。遍历过程中得到的顶点序列称为图遍历序列。 图的遍历过程中根据搜索方法的不同又可以划分为两种搜索策略 (1)深度优先搜索(DFSDepth First Search) (2)广度优先搜索(BFSBreadth First Search)2 深度优先搜索2.1 算法思想 深度优先搜索思想假设初始状态是图中所有顶点均未被访问则从某个顶点v出发首先访问该顶点然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到则另选一个未被访问的顶点作起始点重复上述过程直至图中所有顶点都被访问到为止。2.2 算法特点 深度优先搜索是一个递归的过程。首先选定一个出发点后进行遍历如果有邻接的未被访问过的节点则继续前进。若不能继续前进则回退一步再前进若回退一步仍然不能前进则连续回退至可以前进的位置为止。重复此过程直到所有与选定点相通的所有顶点都被遍历。 深度优先搜索是递归过程带有回退操作因此需要使用栈存储访问的路径信息。当访问到的当前顶点没有可以前进的邻接顶点时需要进行出栈操作将当前位置回退至出栈元素位置。2.3 图解过程2.3.1 无向图深度优先搜索 以图2.3.1.1中所示无向图说明深度优先搜索遍历过程。图2.3.1.1(1)首先选取顶点A为起始点输出A顶点信息且将A入栈并标记A为已访问顶点。(2)A的邻接顶点有C、D、F从中任意选取一个顶点前进。这里我们选取C顶点为前进位置顶点。输出C顶点信息将C入栈并标记C为已访问顶点。当前位置指向顶点C。(3)顶点C的邻接顶点有A、D和B此时A已经标记为已访问顶点因此不能继续访问。从B或者D中选取一个顶点前进这里我们选取B顶点为前进位置顶点。输出B顶点信息将B入栈标记B顶点为已访问顶点。当前位置指向顶点B。(4)顶点B的邻接顶点只有C、EC已被标记不能继续访问因此选取E为前进位置顶点输出E顶点信息将E入栈标记E顶点当前位置指向E。(5)顶点E的邻接顶点均已被标记此时无法继续前进则需要进行回退。将当前位置回退至顶点B回退的同时将E出栈。(6)顶点B的邻接顶点也均被标记需要继续回退当前位置回退至C回退同时将B出栈。(7)顶点C可以前进的顶点位置为D则输出D顶点信息将D入栈并标记D顶点。当前位置指向顶点D。(8)顶点D没有前进的顶点位置因此需要回退操作。将当前位置回退至顶点C回退同时将D出栈。(9)顶点C没有前进的顶点位置继续回退将当前位置回退至顶点A回退同时将C出栈。(10)顶点A前进的顶点位置为F输出F顶点信息将F入栈并标记F。将当前位置指向顶点F。(11)顶点F的前进顶点位置为G输出G顶点信息将G入栈并标记G。将当前位置指向顶点G。(12)顶点G没有前进顶点位置回退至F。当前位置指向F回退同时将G出栈。(13)顶点F没有前进顶点位置回退至A当前位置指向A回退同时将F出栈。(14)顶点A没有前进顶点位置继续回退栈为空则以A为起始的遍历结束。若图中仍有未被访问的顶点则选取未访问的顶点为起始点继续执行此过程。直至所有顶点均被访问。(15)采用深度优先搜索遍历顺序为A-C-B-E-D-F-G。2.3.2 有向图深度优先搜索 以图2.3.2.1中所示有向图说明深度优先搜索遍历过程。图2.3.2.1 有向图(1)以顶点A为起始点输出A将A入栈并标记A。当前位置指向A。(2)以A为尾的边只有1条且边的头为顶点B则前进位置为顶点B输出B将B入栈标记B。当前位置指向B。(3)顶点B可以前进的位置有C与F选取F为前进位置输出F将F入栈并标记F。当前位置指向F。(4)顶点F的前进位置为G输出G将G入栈并标记G。当前位置指向G。(5)顶点G没有可以前进的位置则回退至F将F出栈。当前位置指向F。(6)顶点F没有可以前进的位置继续回退至B将F出栈。当前位置指向B。(7)顶点B可以前进位置为C和E选取E输出E将E入栈并标记E。当前位置指向E。(8)顶点E的前进位置为D输出D将D入栈并标记D。当前位置指向D。(9)顶点D的前进位置为C输出C将C入栈并标记C。当前位置指向C。(10)顶点C没有前进位置进行回退至D回退同时将C出栈。(11)继续执行此过程直至栈为空以A为起始点的遍历过程结束。若图中仍有未被访问的顶点则选取未访问的顶点为起始点继续执行此过程。直至所有顶点均被访问。2.4 算法分析 当图采用邻接矩阵存储时由于矩阵元素个数为n^2因此时间复杂度就是O(n^2)。 当图采用邻接表存储时邻接表中只是存储了边结点(e条边无向图也只是2e个结点)加上表头结点为n(也就是顶点个数)因此时间复杂度为O(ne)。3 广度优先搜索3.1 算法思想 广度优先搜索思想从图中某顶点v出发在访问了v之后依次访问v的各个未曾访问过的邻接点然后分别从这些邻接点出发依次访问它们的邻接点并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问则需要另选一个未曾被访问过的顶点作为新的起始点重复上述过程直至图中所有顶点都被访问到为止。3.2 算法特点 广度优先搜索类似于树的层次遍历是按照一种由近及远的方式访问图的顶点。在进行广度优先搜索时需要使用队列存储顶点信息。3.3 图解过程3.3.1 无向图的广度优先搜索 例如图3.3.1.1所示的无向图采用广度优先搜索过程。图3.3.1.1(1)选取A为起始点输出AA入队列标记A当前位置指向A。(2)队列头为AA出队列。A的邻接顶点有B、E输出B和E将B和E入队并标记B、E。当前位置指向A。(3)队列头为BB出队列。B的邻接顶点有C、D输出C、D将C、D入队列并标记C、D。当前位置指向B。(4)队列头为EE出队列。E的邻接顶点有D、F但是D已经被标记因此输出F将F入队列并标记F。当前位置指向E。(5)队列头为CC出队列。C的邻接顶点有B、D但B、D均被标记。无元素入队列。当前位置指向C。(6)队列头为DD出队列。D的邻接顶点有B、C、E但是B、C、E均被标记无元素入队列。当前位置指向D。(7)队列头为FF出队列。F的邻接顶点有G、H输出G、H将G、H入队列并标记G、H。当前位置指向F。(8)队列头为GG出队列。G的邻接顶点有F但F已被标记无元素入队列。当前位置指向G。(9)队列头为HH出队列。H的邻接顶点有F但F已被标记无元素入队列。当前位置指向H。img(10)队列空则以A为起始点的遍历结束。若图中仍有未被访问的顶点则选取未访问的顶点为起始点继续执行此过程。直至所有顶点均被访问。3.3.2 有向图的广度优先搜索 以图3.3.2.1所示的有向图为例进行广度优先搜索。3.3.2.1(1)选取A为起始点输出A将A入队列标记A。(2)队列头为AA出队列。以A为尾的边有两条对应的头分别为B、C则A的邻接顶点有B、C。输出B、C将B、C入队列并标记B、C。(3)队列头为BB出队列。B的邻接顶点为CC已经被标记因此无新元素入队列。(4)队列头为CC出队列。C的邻接顶点有E、F。输出E、F将E、F入队列并标记E、F。(5)队列头为EE出队列。E的邻接顶点有G、H。输出G、H将G、H入队列并标记G、H。(6)队列头为FF出队列。F无邻接顶点。(7)队列头为GG出队列。G无邻接顶点。(8)队列头为HH出队列。H邻接顶点为E但是E已被标记无新元素入队列。(9)队列为空以A为起始点的遍历过程结束此时图中仍有D未被访问则以D为起始点继续遍历。选取D为起始点输出D将D入队列标记D。(10)队列头为DD出队列D的邻接顶点为BB已被标记无新元素入队列。(11)队列为空且所有元素均被访问广度优先搜索遍历过程结束。广度优先搜索的输出序列为A-B-E-C-D-F-G-H。3.4 算法分析 假设图有V个顶点E条边广度优先搜索算法需要搜索V个节点时间消耗是O(V)在搜索过程中又需要根据边来增加队列的长度于是这里需要消耗O(E)总得来说效率大约是O(VE)。4 总结 图的遍历主要就是这两种遍历思想深度优先搜索使用递归方式需要栈结构辅助实现。广度优先搜索需要使用队列结构辅助实现。在遍历过程中可以看出对于连通图从图的任意一个顶点开始深度或广度优先遍历一定可以访问图中的所有顶点但对于非连通图从图的任意一个顶点开始深度或广度优先遍历并不能访问图中的所有顶点。日常推荐漫话如何给女朋友解释什么是Git和GitHub阿广自掏腰包赠送8套鼠标键盘年薪80万的大数据开发全套教程都在这儿今日问题图有的两种遍历方式是什么各种的优缺点是什么打卡格式打卡第n天答xxx给个在看代码无 Bug??
