首页 计算机科学 数据结构

# 图的广度优先遍历

广度优先遍历要点：

  • 找到与一个顶点相邻的所有顶点

  • 标记哪些顶点被访问过

  • 需要一个辅助队列

  • 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);           //初始化辅助队列Q
    for(i=0;i<G.vexnum;++i) //从0号节点开始遍历
        if(!visited[i])     //对每个连通分量调用一次BFS
            BFS(G,i);       //vi未访问过，从vi开始BFS
}
//广度优先遍历
void BFS(Graph G,int v){    //从顶点v出发，广度优先遍历
    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]){ //w为v的尚未访问的邻接点
                visit(w);    //访问顶点w
                visited[w]=true;   //对w做已访问标记
                EnQueue(Q,w); //顶点w入队
            }
    }
}

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

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

结论：对于无向图，调用 BFS 函数的次数 = 连通分量数

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

  • 邻接矩阵存储的图
    • 访问 | V | 个顶点需要 O (|V|) 的时间
    • 查找每个顶点的邻接点都需要 O (|V|) 的时间，而总共有 | V | 个顶点，时间复杂度 = O (|V|*|V|)
  • 邻接表存储的图
    • 访问 | V | 个顶点需要 O (|V|) 的时间
    • 查找各个顶点的邻接点共需要 O (|E|) 的时间，时间复杂度 = O (|V|+|E|)

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

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

# 图的深度优先遍历

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

void DFSTranverse(Graph G){
    for(i=0;i<G.vexnum;++i)
        visited[i]=false;   //访问标记数组初始化
    for(i=0;i<G.vexnum;++i) //从0号节点开始遍历
        if(!visited[i])     //对每个连通分量调用一次DFS
            DFS(G,i);       //vi未访问过，从vi开始DFS
}

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为v的尚未访问的邻接点
            DFS(G,w);
}

空间复杂度：来自函数调用栈，最坏情况，递归深度为 O (|V|)

时间复杂度 = 访问各结点所需时间 + 探索各条边所需时间

  • 邻接矩阵存储的图
    • 访问 | V | 个顶点需要 O (|V|) 的时间
    • 查找每个顶点的邻接点都需要 O (|V|) 的时间，而总共有 | V | 个顶点，时间复杂度 = O (|V|*|V|)
  • 邻接表存储的图
    • 访问 | V | 个顶点需要 O (|V|) 的时间
    • 查找各个顶点的邻接点共需要 O (|E|) 的时间，时间复杂度 = O (|V|+|E|)

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

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

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

对无向图进行 BFS/DFS 遍历，调用 BFS/DFS 函数的次数 = 连通分量数

对于连通图，只需要调用 1 次 BFS/DFS

对有向图进行 BFS/DFS 遍历，调用 BFS/DFS 函数的次数需要具体问题具体分析

若起始顶点到其他各顶点都有路径，则只需要调用 1 次 BFS/DFS 函数

对于强连通图，从任意结点出发都只需要调用 1 次 BFS/DFS 函数