一个图 经过 深度优先遍历后 生产的是一颗什么树··（我知道是深度优先树） 但这个树的特点和性质是什么
发布网友
发布时间：2022-05-08 15:34
共2个回答
热心网友
时间：2024-01-25 17:12
图的深度优先遍历类似于树的先序遍历。
特点是尽可能先往深方向进行搜索。
所以，从这可以知道，遍历的第一个点将是生成树的根节点。
每个顶点至多调用一次DFS函数。而且一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。
遍历图的过程实质上是对每个顶点查找其邻接点的过程。
其耗费的时间则取决于所采用的存储结果。
当用邻接矩阵表示图时，查找每个顶点的邻接点的时间复杂度为O(n平方)。n为顶点数
而当用邻接表做图的存储结构时，找邻接点的时间复杂度为O(e)。e为图中边数。
由此，当以邻接表做存储结构时，深度优先搜索遍历图的时间复杂度为O(n+e)。
希望我的回答对您有帮助~
参考资料：by 5220
来自：求助得到的回答
热心网友
时间：2024-01-25 17:13
