图的深度优先遍历和广度优先遍历

[jyzwf]

广度优先遍历

类似于树的层次遍历，必须借助一个队列来记忆正在访问的顶点的下一层代码

当各边权值相等时可以解决单源最短路径问题

伪代码

bool visited[MAX_VERTEX_NUM]; // 访问标记数组

void BFSTraverse(Graph G){
    // 对图进行广度优先遍历，设访问函数为 visit()
    for (i = 0; i < G.vexnum; ++i){
        visited[i] = false; //访问标记数组
    }

    InitQueue(Q); // 初始化辅助队列

    for (i = 0; i < G.vexnum; ++i){
        if (!visited[i]) // 对每个连通分量进行一次 BFS
            BFS(G, i);
    }
}

void BFS(Graph G, int v){
    visit(v); // 访问初始顶点
    visited[v] = true;

    Enqueue(Q, v); // 顶点 v 入队列

    while (!isEmpty(Q)){
        Dequeue(Q, v); // 顶点 v 出队列

        for (w = FirstNeighbor(G, v); w > = 0; w = NextNeighbor(G, v, w)){

            if (!visited[w]){  // w 为没有被访问的 v 的邻接顶点
                visit(w);
                visited[w] = true;
                Enqueue(Q, w) // 顶点 w 入列
            }// if

        }// for

    }// while
}

性能分析

由于他要借助一个辅助队列 Q，所以他的空间复杂度为 O(|V|) ，其中 V 为顶点个数
如果采用 邻接表 存储，则时间复杂度为 O(|E|)，总的为 O(|V| + |E|)
如果采用 邻接矩阵存储，总的复杂度为 O( |V| * |V|)

深度优先遍历

bool visited[MAX_VERTEX_NUM]; // 访问标记数组

void DFSTraverse(Graph G){
    // 对图进行深度优先遍历，设访问函数为 visit()
    for (i = 0; i < G.vexnum; ++i){
        visited[i] = false; //访问标记数组
    }


    for (i = 0; i < G.vexnum; ++i){
        if (!visited[i]) // 对每个连通分量进行一次 DFS
            DFS(G, i);
    }
}

void DFS(Graph G, int v){
    // 使用递归

    visit(v); // 访问初始顶点
    
    visited[i] = true


    for (w = FirstNeighbor(G, v); w > = 0; w = NextNeighbor(G, v, w)){

        if (!visited[w]){  // w 为没有被访问的 v 的邻接顶点
            
            DFS(G,w)
               
        }// if

    }// for

}

性能分析

由于他要借助一个递归栈，所以他的空间复杂度为 O(|V|) ，其中 V 为顶点个数
如果采用 邻接表 存储，则时间复杂度为 O(|E|)，总的为 O(|V| + |E|)
如果采用 邻接矩阵存储，总的复杂度为 O( |V| * |V|)