【数据结构】图的遍历--广度优先搜索

深碍√TFBOYSˉ_ 2022-06-17 08:47 199阅读 0赞

广度优先搜索过程类似于树的层次遍历，假设从图中某顶点i出发，在访问i之后依次访问i的各个未被访问的邻接点，然后从这些邻接点出发依次访问他们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直到所有顶点都被访问到（限于连通图）。如果是非连通图，则从未被访问的顶点中任选一个，再次重复上述过程。  
换句话说，广度优先搜索过程中其实是以顶点i为起始点，由近及远，依次访问了与i路径相通且路径长度为1，2，··· ···的顶点。  
根据广度优先搜索的特点，可以使用队列来保证访问的次序。每访问一个顶点就将该顶点入队，之后从队首取出一个顶点，依次访问该顶点未被访问过的邻接点，并入队。重复该过程，直到队列为空，则一个连通分量的遍历完成。

![SouthEast][]

以该无向图为例，以A为起点，字母序访问邻接点，其广度优先搜索结果为：
                             A B C D F H E G I

下面给出**邻接矩阵**存储图的广度优先搜索算法的代码描述。

void BFS_M(MGraph G)
    {
        Queue Q;
        int t;
        Q = CreateQ();
        for(int i = 0; i < G->n; i++)
            G->Visited[i] = 0;
        for(int i = 0; i < G->n; i++){
            if(!G->Visited[i]){
                printf("%c ", G->Vertices[i]);
                G->Visited[i] = 1;
                AddQ(Q,i);
                while(!IsEmptyQ(Q)){
                    t = DeleteQ(Q);
                    for(int j = 0; j < G->n; j++)
                    if(G->Edges[t][j] != INFINITY && !G->Visited[j]){
                        printf("%c ", G->Vertices[j]);
                        G->Visited[j] = 1;
                        AddQ(Q,j);
                    }
                }
            }
            printf("\n");
        }
    }

[SouthEast]: /images/20220617/c78f19425bab40e99551ee1c22046680.png