深度优先遍历(DFS)Depth First search
连通图的深度优先遍历类似与树的先根遍历
算法实现
DFS结果是213546
效率分析
■用邻接矩阵来表示图,遍历图中每一个顶点都要从头扫描该顶点所在行
行,时间复杂度为O(n7)。
■用邻接表来表示图,虽然有2e个表结点,但只需扫描e个结点即可
完成遍历,加上访问n个头结点的时间,时间复杂度为O(n+ e)。
结论:
稠密图适于在邻接矩阵.上进行深度遍历;
稀疏图适于在邻接表上进行深度遍历。
广度优先遍历(BFS)Breadth First Search
BFS算法效率分析
●如果使用邻接矩阵,则BFS对于每个被访问到的顶点, 都要循巩
检测矩阵中的整整一行( n个元素) ,总的时间代价为O(n7)。
●用邻接表来表示图,虽然有2e个表结点,但只需扫描e个结点即
可完成遍历,加上访问n个头结点的时间,时间复杂度为O(n+e)。
DSF和BSF比较
●空间复杂度相同,都是O(n)(借用了堆栈或队列) ;
●时间复杂度只与存储结构(邻接矩阵或邻接表)有关,而与搜索路径无
关。