数据结构笔记——图的深度优先遍历(DFS)
写在前面:科班出身,应届考研党,愿21考研成功上岸,冲冲冲!
目录
一、树的深度优先遍历
void PreOrder(TreeNode *R){
if(R != NULL){
visit(R);
while(R还有下一个子树T)
PreOrder(T);
}
}
树的深度优先遍历(先根、后根):
从根节点出发,能往更深处走就走。每当访问一个结点的时候,要检查是否还有与当前结点相邻的且没有被访问过的结点,如果有的话就往下一层钻。
注:新找到的相邻结点一定是没有访问过的
下图先根遍历序列:12563478
二、图的深度优先遍历
bool visited[MAX_VERTEX_NUM]; //访问标记数组
void DFS(Graph G,int v){ //从顶点v出发,深度优先遍历图G
visit(v); //访问顶点v
visited(v) = TRUE; //设已访问标记
for(w = FirstNeighbor(G,v); w >= 0; w = NextNeighbor(G,v,w))
if(!visited[w]) //w为u的尚未访问的邻接顶点
DFS(G,w);
}
三、算法存在的问题
如果是非连通图图,则无法遍历完所有结点
四、DFS算法(Final版)
bool visited[MAX_VERTEX_NUM]; //访问标记数组
void DFSTraverse(Graph G){
for(v = 0; v < G.vexnum;++v)
visited[v] = FALSE;
for(v = 0; v < G.vexnum;++v)
if(!visited[v])
DFS(G,v);
}
void DFS(Graph G,int v){ //从顶点v出发,深度优先遍历图G
visit(v); //访问顶点v
visited(v) = TRUE; //设已访问标记
for(w = FirstNeighbor(G,v); w >= 0; w = NextNeighbor(G,v,w))
if(!visited[w]) //w为u的尚未访问的邻接顶点
DFS(G,w);
}
五、复杂度分析
空间复杂度
最坏情况:递归深度为O(|V|)
最好情况:O(1)
时间复杂度
时间复杂度=访问各结点所需时间+探索各条边所需时间
邻接矩阵存储的图:
访问|V|个顶点需要O(|V|)的时间
查找每个顶点的邻接点都需要O(|V|)的时间,而总共有|V|个顶点
时间复杂度:O(|V|^2)
邻接表存储的图:
访问|V|个顶点需要O(|V|)的时间
查找各个顶点的邻接点共需要O(|E|)的时间
查找各个顶点的邻接点共需要O(|E|)的时间
时间复杂度= O(|V|+|E|)
六、深度优先遍历序列
从2出发的深度优先遍历序列:21563478
从3出发的深度优先遍历序列:34762158
从1出发的深度优先遍历序列:12634785
注:
同一个图的邻接矩阵表示方式唯一,因此深度优先遍历序列唯一
同一个图的邻接表表示访问不唯一,因此深度优先遍历序列不唯一
七、深度优先生成树
同一个图的邻接矩阵表示方式唯一,因此深度优先遍历序列唯一,深度优先生成树也唯一
同一个图的邻接表表示访问不唯一,因此深度优先遍历序列不唯一,深度优先生成树也不唯一
八、深度优先生成树森林
九、图的遍历与图的连通性
对无向图进行BFS/DFS遍历,调用BFS/DFS函数的次数=连通分量数
对于连通图,只需调用1次BFS/DFS
对有向图进行BFS/DFS遍历,调用BFS/DFS函数的次数要具体问题具体分析
若起始顶点到其他各顶点都有路径,则只需调用1次BFS/DFS函数
对强连通图,从任一结点出发都只需调用1次BFS/DFS
十、总结
更多推荐
所有评论(0)