【数据结构】图的遍历—广度优先遍历、深度优先遍历

1. 图的广度优先遍历

1. 回顾二叉树的层序遍历

【数据结构】二叉树的先中后序遍历与层序遍历

层序遍历也叫层次遍历，也叫广度优先遍历。

算法思想：

初始化一个辅助队列。
根结点入队。
若队列非空，则队头结点出队，访问该节点。并将其左、右孩子插入队尾（如果有的话）。
重复3的步骤直至队列为空。

2. 图的广度优先遍历

要点：

找到与一个顶点相邻的所有顶点。
标记哪些顶点被访问过。
需要一个辅助队列。

FirstNeighbor(G,x):求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。

NextNeighbor(G,x,y):假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。

bool visited[MAX_VERTEX_NUM];  // 访问标记数组，初始都为false

// 广度优先遍历
void BFS(){
    visit(v);  // 访问初始顶点v
    visited[v]=true;  // 对v做已访问标记
    Enqueue(Q,v);  // 顶点v入队列Q
    while(!isEmpty(Q)){
        DeQueue(Q,v);  // 顶点v出队列
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
            // 检测v所有邻接点
            if(!visited[w]){
                visit(w);  // 访问顶点w
                visited[w]=true;  // 对w做已访问标记
                EnQueue(Q,w);  // 顶点w入队列
            }
        }
    }
}

// 对图G进行广度优先遍历
void BFSTraverse(Graph G){
    for(i=0;i<G.vexnum;++i){
        visited[i]=false;  // 访问标记数组初始化
    }
    InitQueue(Q);  // 初始化辅助队列Q
    for(i=0;i<G.vexnum;++i){  // 从0号顶点开始遍历
        if(!visited[i]){  // 对每个连通分量调用一次BFS
            BFS(G,i);  // vi未访问过，从vi开始BFS
        }
    }
}

说明：BFSTraverse多加了一层for循环，是为了如果有多个连通分量的情况，可以遍历数组，从false的结点处开始遍历。

3. 广度优先遍历序列

从顶点1出发得到的广度优先遍历序列： 1、2、5、6、3、7、4、8

从顶点3出发得到的广度优先遍历序列： 3、4、6、7、8、2、1、5

注意：

同一个图的邻接矩阵表示方式唯一，因此广度优先遍历序列唯一。
同一个图的邻接表表示方式不唯一，因为广度优先遍历序列不唯一。
一般按照序号顺序。

4. 复杂度分析

空间复杂度：

最坏情况，一个顶点连接了尽可能多的顶点，辅助队列大小为O(|V|)。

时间复杂度：

5. 广度优先生成树、森林

注意：广度优先生成树由广度优先遍历过程确定。由于邻接表的表示方式不唯一，因此基于邻接表的广度优先生成树也不唯一。

说明：对于非连通图的广度优先遍历，可得到广度优先生成森林。

2. 图的深度优先遍历

1. 回顾二叉树的深度优先遍历

【数据结构】二叉树的先中后序遍历与层序遍历

根左右（NLR）

先序遍历也叫深度优先遍历。

先序遍历操作过程如下：

若二叉树为空，则什么也不做；
若二叉树非空：

访问根结点；
先序遍历左子树；
先序遍历右子树。

树的深度优先遍历：从根结点出发，能往更深处走就尽量往深处走。每当访问一个结点的时候，要检查是否还有与当前结点相邻的且没有被访问过的结点，如果有的话就往下层走。

图的深度优先遍历类似于树的先根遍历。

2. 图的深度优先遍历

bool visited[MAX_VERTEX_NUM];  // 访问标记数组，初始都为false
// 深度优先遍历图G
void DFS(Graph G,int v){
    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);
        }
    }
}
// 对图G进行深度优先遍历
void DFSTraverse(Graph G){
    for(v=0;v<G.vexnum;++v){
        visited[v]=false;  // 初始化以访问标记数据
    }
    for(v=0;v<G.vexnum;++v){  // 本代码中是v0开始遍历
        if(!visited[v]){
            DFS(G,v);
        }
    }
}