当前位置：首页 > 正文

数据结构中出图的二种遍历，写出算法与思想，谢谢

作者：Judy发布时间：2023-02-12浏览：456

BFS，广度优先搜索先遍历离起点近的，再到远的，直至全图。先遍历所有与起点距离为1的点，再到所有距离为2的点……具体实现，需要一个队列进行辅助存储。

举个例，S为起点，S到A,B,C3个点相邻。

A又与A1,A2相邻，B与B1,B2相邻，C没有与其他点相邻。对于遍历A发生的事情，就是“发现”了A1,A2。但是，这是不能立即遍历A1,A2，这与BFS宗旨违背，必须先遍历B,C。而又由于B,C肯定是比A1,A2先“发现”，这就体现了一种“先进先出”的性质，因而需要队列对为扩展的结点进行暂存BFS(){queue q;q.push(s);//一开始的s点while(q非空){从q中取一元素将该元素“发现”，而又未被进过q的结点入队}}DFS，深度优先搜索先选定一条路径，对路径上的点进行遍历。

然后，从路径的尽头开始，逐步回退，在每个分支再遍历其他路径及其上面的点。具体实现，常写作递归，故可理解为通过栈辅助存储。还是上面的距离，DFS出来的其中一种序列是S,A,A1,A2,B,B1,B2,C。

路径S,A,A1为第一选取的路径，然后回退，逐步选取其他分支，在A选取了A2作为第二路径，以此类推。由于这样对每个点所做的操作就是“发现”，“遍历”与“回退”，操作种类相同，故常写作递归。

声明：部分资源转载自互联网，转载目的在于传递更多知识，并不代表本网赞同其观点和对其真实性负责。如有侵权或者知识有谬误之处，麻烦通知删除，谢谢！联系方式: zzsla2022#163.com

数据结构中出图的二种遍历，写出算法与思想，谢谢

相关推荐

Copyright zzsla.top Rights Reserved.

京公网安备11011502037736