小小林熬夜学编程

这个屌丝很懒，什么也没留下！

热门标签

数据结构笔记——图的深度优先遍历（DFS）

作者：小小林熬夜学编程 | 2024-04-29 20:44:33

踩

图的深度优先遍历

写在前面：科班出身，应届考研党，愿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);
}