5.4 图的遍历

5.4.1 图的遍历

广度优先遍历、深度优先遍历

5.4.2 广度优先遍历（BFS）

与树的广度优先搜索（层次遍历）很像。

需要一个辅助链队列。

树的层次遍历的算法思想：

• ①初始化一个辅助队列（链队列）
• ②根结点入队
• ③若队列非空，则队头结点出队，访问该结点并将其左、右孩子插入队尾(如果有的话)
• ④重复③直至队列为空

图的广度优先搜索的算法思想：

• ①初始化一个辅助队列（链队列）
• ②结点入队
• ③若队列非空，则队头结点出队，访问该结点并将其相邻顶点插入队尾(如果有的话)
• ④重复③直至队列为空

树没有回路，不可能搜到已访问结点 图有可能搜索到已访问的结点 解决方法：用一个数组标记顶点的访问

链队列

//类型描述
typedef struct LNode{    //定义单链表结点类型
	ElemType data;            //数据域，可以是别的各种数据类型，本文统一用int类型
	struct LNode *next;  //指针域
}LNode;
typedef struct{
    LNode *front, *rear;
}LinkQueue;

代码

//树的层次遍历（广度优先搜索）（用二叉树的链式存储）
void LevelOrder(BiTree T){
    LinkQueue Q;
    InitQueue(Q);
    BiTree p;   //T为根结点，p也是根结点，保证根出队后可以指向孩子，因为T出队后，T->lchild无效
    EnQueue(Q, T);        //根结点入队
    while(!isEmpty(Q)){   //队列不空则循环
        DeQueue(Q, T);    //根结点出队
        if(p->lchild!=NULL)
            EnQueue(Q, p->lchild);        //左结点入队
        if(p->rchild!=NULL)
            EnQueue(Q, p->rchild);        //右结点入队
    }
}

//图的广度优先搜索（用图的邻接矩阵、领接表都可以，只是FirstNeighbor和NextNeighbor函数实现不一样）
bool visited[MAX_VERTEX_NUM];     //访问标记数组
void BFSTraverse(Graph G){        //对图G进行广度优先搜索
    for(v=0; v<G.vexnum; ++v){
        visited[v] = false;       //初始化访问标记数组
    }
    InitQueue(Q);                 //初始化辅助队列Q
    for(v=0; v<G.vexnum; ++v){
        if(!visited[v]){          //对每个连通分量调用一次BFS
            BFS(G,v);             //vi没访问过，从vi开始BFS
        }
    }
}
void BFS(Graph G, int v){
	visit(v);             //访问初始顶点v
    visited[v] = true;    //对v做已访问标记
    EnQueue(Q, v);        //顶点v入队
    while(!isEmpty(Q)){   //队列不空则循环
        DeQueue(Q, v);    //顶点v出队
        for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w)){//检测v所有的邻接顶点
            if(!visited[w]){          //w为v尚未访问的邻接顶点
				visit(w);             //访问顶点w
    			visited[w] = true;    //对w做已访问标记
                EnQueue(Q, w);        //顶点w入队
            }
        }
    }
}

复杂度分析

空间复杂度=$O(|V|)$

时间复杂度： 邻接矩阵=$O(|V|^2)$，邻接表=$O(|V|+|E|)$

原理：

• 邻接矩阵：访问点=$O(|V|)$，访问边=$O(|V|^2)$，时间复杂度=$O(|V|)+O(|V|^2)=O(|V|^2)$

• 邻接表：访问点=$O(|V|)$，访问无向边=$O(2|E|)$，访问无向边=$O(|E|)$， 无向图时间复杂度=$O(|V|)+O(2|E|)=O(|V|+|E|)$有向图时间复杂度=$O(|V|)+O(|E|)=O(|V|+|E|)$

广度优先生成树、森林

连通图生成树，非连通图生森林

由于领接矩阵表示法唯一，领接表法表示不唯一 导致邻接矩阵生成树唯一，领接表生成树不唯一

5.4.3 深度优先遍历（DFS）

代码

与树的先序遍历很像。

//树的先序遍历（深度优先遍历）（用二叉树的链式存储）
void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);               //访问根结点
        PreOrder(T->lchild);	//递归遍历左子树
        PreOrder(T->rchild);	//递归遍历右子树
    }
}

//图的深度优先搜索（用图的邻接矩阵、领接表都可以，只是FirstNeighbor和NextNeighbor函数实现不一样）
bool visited[MAX_VERTEX_NUM];     //访问标记数组
void BFSTraverse(Graph G){        //对图G进行广度优先搜索
    for(v=0; v<G.vexnum; ++v){
        visited[v] = false;       //初始化访问标记数组
    }
    for(v=0; v<G.vexnum; ++v){
        if(!visited[v]){          //对每个连通分量调用一次BFS
            BFS(G,v);             //vi没访问过，从vi开始BFS
        }
    }
}
void DFS(Graph G, int v){
    visit(v);             //访问初始顶点v
    visited[v] = true;    //对v做已访问标记
    for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w)){//检测v所有的邻接顶点
        if(!visit[w]){          //w为v尚未访问的邻接顶点
            DFS(G, w);
        }
    }
}

复杂度分析（与BFS一样）

空间复杂度=$O(|V|)$，来自递归工作站

时间复杂度： 邻接矩阵=$O(|V|^2)$，邻接表=$O(|V|+|E|)$

原理：

• 邻接矩阵：访问点=$O(|V|)$，访问边=$O(|V|^2)$，时间复杂度=$O(|V|)+O(|V|^2)=O(|V|^2)$
• 邻接表：访问点=$O(|V|)$，访问无向边=$O(2|E|)$，访问无向边=$O(|E|)$， 无向图时间复杂度=$O(|V|)+O(2|E|)=O(|V|+|E|)$有向图时间复杂度=$O(|V|)+O(|E|)=O(|V|+|E|)$

深度优先生成树、森林（与BFS一样）

连通图生成树，非连通图生森林

由于领接矩阵表示法唯一，领接表法表示不唯一 导致邻接矩阵生成树唯一，领接表生成树不唯一

5.4.4 图的遍历与图的连通性

无向图进行BFS/DFS遍历：调用BFS/DFS次数=连通分量数 连通图只需调用一次BFS/DFS

有向图进行BFS/DFS遍历：要具体分析 若起始顶点到其它顶点都有路径，则只需调用一次 强连通图从任意结点都只需调用一次BFS/DFS