数据结构(六)——图的遍历

6.3 图的遍历

6.3.1 图的广度优先遍历

⼴度优先遍历（Breadth-First-Search, BFS）要点：
1. 找到与⼀个顶点相邻的所有顶点
2. 标记哪些顶点被访问过
3. 需要⼀个辅助队

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

//广度优先遍历
void BFS(Graph G,int v){        //从顶点v开始广度优先遍历图G
    visit(G,v);					//访问图G的结点v
    visited[v]=TREE;			//对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]){    //w为v的尚未访问的邻接顶点
                visit(w);       //访问顶点w
                visited[w]=TREE;//对w做已访问标记
                EnQueue(Q,w);   //顶点w入队列
            }
        }
    }
}

复杂度分析

空间复杂度：最坏情况，辅助队列大小为O(|V|)

邻接矩阵存储的图：
访问 |V| 个顶点需要O(|V|)的时间
查找每个顶点的邻接点都需要O(|V|)的时间，⽽总共有|V|个顶点
时间复杂度= O(|V|^2)

邻接表存储的图：
访问 |V| 个顶点需要O(|V|)的时间
查找各个顶点的邻接点共需要O(|E|)的时间
时间复杂度= O(|V|+|E|)

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

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

6.3.1 图的深度优先遍历

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

// 对图G进行深度优先算法
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(G,v);              //访问顶点v
    visited[v]=TREE;         //设已访问标记
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v)){
        if(!visited[w])
            DFS(G,v);        //w为u的尚未访问的邻接顶点
    }
}

复杂度分析
空间复杂度:来自函数调用栈
最坏情况递归深度为O(|V|)
最好情况O(1)

时间复杂度=访问各结点所需时间+探索各条边所需时间
邻接矩阵存储的图:
访问|V|个顶点需要O(|V|)的时间
查找每个顶点的邻接点都需要O(|V|)的时间，而总共有|N个顶点时间复杂度=O(|V|^2)

邻接表存储的图:
访问V个顶点需要O(|V|)的时间
查找各个顶点的邻接点共需要O(E)的时间,时间复杂度=O(|V|+|E|)

同一个图的邻接矩阵表示方式唯一，因此深度优先遍历序列唯一
同一个图邻接表表示方式不唯一，因此深度优先遍历序列不唯一

图的遍历与图的连通性