数据结构基础图的遍历（二）之 BFS

冷不防 2022-08-02 05:55 163阅读 0赞

*  广度优先遍历

> 广度优先遍历也叫广度优先搜索(Breadth First Search)。
> 
> 它的遍历规则：
> 
> 1.先访问完当前顶点的所有邻接点。(应该看得出广度的意思)  
> 2.先访问顶点的邻接点先于后访问顶点的邻接点被访问。  
> 
> 
>   
> 
> 
> 给定一图G=<V,E>，用visited\[i\]表示顶点i的访问情况，则初始情况下所有的visited\[i\]都为false。假设从顶点V0开始遍历，且顶点V0的邻接点，从小到大有Vi、Vj...Vk。按规则1，接着应遍历Vi、Vj ... Vk。再按规则2，接下来应遍历Vi的所有邻接点，之后是Vj的所有邻接点，...，最后是Vk的所有邻接点。接下来就是递归的过程...
> 
> 在广度遍历的过程中，会出现图不连通的情况，此时也需按上述情况二来进行：测试visited\[i\]...。在上述过程中，可以看出需要用到队列。

*  **遍历分析**

![Center][]

> 从V0开始遍历，V0有两个邻接点V1和V2，于是按序遍历V1、V2。V1先于V2被访问，于是V1的邻接点应先于V2的邻接点被访问，那就是接着访问V3。V2无邻接点，只能看V3的邻接点了，而V0已被访问过了。此时需检测visited\[i\]，只有V4了。广度遍历完毕。  
> 遍历序列是  
> V0->V1->V2->V3->V4。  
> 从其它顶点出发的广度优先遍历序列是  
> V1->V3->V0->V2->V4。  
> V2->V0->V1->V3->V4。  
> V3->V0->V1->V2->V4。  
> V4->V2->V0->V1->V3。  
> 以上结果，我们同样用于测试程序。

*  代码实现

// 邻接矩阵的STL实现 BFS
    Status InitQueue(Queue *Q)  
    {  
        Q->front=0;  
        Q->rear=0;  
        return  OK;  
    }  
    void BFSTraverse(MGraph G)  
    {  
        //按广度优先非递归地遍历图G。使用辅助队列Q和访问标志数组visited  
        int v, w, u;  
        Queue Q;  // 自定义数据结构 - 队列
         // front;      /* 头指针 */  
         // rear;       /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */  
     
        for(v=0; v<G.vexnum; ++v)    // 访问标志数组初始化  
            visited[v] = false;  
     
        InitQueue(Q);               // 置空的辅助队列  
     
        for(v=0; v<G.vexnum; ++v)  
            if(!visited[v])  
            {  
                visited[v] = true;  
                VisitFunc(v);  
                EnQueue(Q,v);   // 入队
                while(QueueEmpty(Q) == FALSE){  
                    DeQueue(Q, u);  //对头元素出队，并置为u  
                    for(w = FirstAdjVex(G,v); w>=0; w=NextAdjVex(G, v, w))  
                        if(!visited[w]){    // w为u未访问的邻接顶点  
                            visited[w] = true;  
                            VisitFunc(w);   // 自定义函数 - 输出节点数据
                            EnQueue(Q, w);  
                        }  
                }  
            }//if  
    }//BFSTraverse  
    int FirstAdjVex(MGraph G, int v)  
    {   //返回节点v的第一个邻接顶点  
        int i;  
        for(i=0; i<G.vexnum; ++i)  
            if(G.arcs[v][i].adj != 0 && i!=v)  
                return i;  
        return -1;          //如果没有，返回-1  
    }  
    int NextAdjVex(MGraph G, int v, int w)  
    {  
        //返回节点v的邻接顶点中w之后的下一个邻接顶点  
        int i;  
        for(i=w+1; i<G.vexnum; ++i)  
            if(G.arcs[v][i].adj != 0 && i!=v)  
                return i;  
        return -1;          //如果没有，返回-1  
    }

// 邻接表的STL实现 BFS
    void BFSTraverse(GraphAdjList GL)  
    {  
        int i;  
        EdgeNode *p;  
        Queue Q;  
        for(i = 0; i < GL->numVertexes; i++)  
            visited[i] = FALSE;  
        InitQueue(&Q);  
        for(i = 0; i < GL->numVertexes; i++)  // 第一层循环
        {  
            if (!visited[i])  
            {  
                visited[i]=TRUE;  
                printf("%c ",GL->adjList[i].data);/* 打印顶点,也可以其它操作 */  
                EnQueue(&Q,i);  // 入队
                while(!QueueEmpty(Q))  // 第二层循环
                {
                    DeQueue(&Q,&i);  // 出队
                    p = GL->adjList[i].firstedge;    /* 找到当前顶点的边表链表头指针 */  
                    while(p)  // 第三层循环
                    {  
                        if(!visited[p->adjvex])  /* 若此顶点未被访问 */  
                        {  
                            visited[p->adjvex]=TRUE;  
                            printf("%c ",GL->adjList[p->adjvex].data);  
                            EnQueue(&Q,p->adjvex);   /* 将此顶点入队列 */  
                        }  
                        p = p->next; /* 指针指向下一个邻接点 */  
                    }  
                }  
            }  
        }  
    }  
    Status EnQueue(Queue *Q,int e)  
    {  
        if ((Q->rear+1)%MAXSIZE == Q->front)  /* 队列满的判断 */  
            return ERROR;  
        Q->data[Q->rear]=e;           /* 将元素e赋值给队尾 */  
        Q->rear=(Q->rear+1)%MAXSIZE;/* rear指针向后移一位置, */  
                                    /* 若到最后则转到数组头部 */  
        return  OK;  
    }  
      
    /* 若队列不空,则删除Q中队头元素,用e返回其值 */  
    Status DeQueue(Queue *Q,int *e)  
    {  
        if (Q->front == Q->rear)          /* 队列空的判断 */  
            return ERROR;  
        *e=Q->data[Q->front];             /* 将队头元素赋值给e */  
        Q->front=(Q->front+1)%MAXSIZE;    /* front指针向后移一位置, */  
                                        /* 若到最后则转到数组头部 */  
        return  OK;  
    }

【数组邻接表采用指针实现广度优先遍历（不推荐）】

/* 
    广度优先搜索 
    从vertex开始遍历，visit是遍历顶点的函数指针 
    */  
    void Graph::bfs(int vertex, void(*visit)(int))  
    {  
        //使用队列  
        queue<int> q;  
        //visited[i]用于标记顶点i是否被访问过  
        bool *visited = new bool[numV];  
        //count用于统计已遍历过的顶点数  
        int i, count;  
        for (i = 0; i < numV; i++)  
            visited[i] = false;  
        q.push(vertex);  
        visit(vertex);  
        visited[vertex] = true;  
        count = 1;  
        while (count < numV)  
        {  
            if (!q.empty())  
            {  
                vertex = q.front();  
                q.pop();  
            }  
            else  
            {  
                for (vertex = 0; vertex < numV && visited[vertex]; vertex++);  
                visit(vertex);  
                visited[vertex] = true;  
                count++;  
                if (count == numV)  
                    return;  
                q.push(vertex);  
            }  
            //代码走到这里，vertex是已经访问过的顶点  
            for (int i = 0; i < numV; i++)  
            {  
                if (!visited[i] && matrix[vertex][i] > 0 && matrix[vertex][i] < MAXWEIGHT)  
                {  
                    visit(i);  
                    visited[i] = true;  
                    count ++;  
                    if (count == numV)  
                        return;  
                    q.push(i);  
                }  
            }  
        }  
        delete[]visited;  
    }  
    void visit(int vertex)  
    {  
        cout << setw(4) << vertex;  
    }  
    int main()  
    {  
        cout << "******图的遍历：深度优先、广度优先***by David***" << endl;  
        bool isDirected, isWeighted;  
        int numV;  
        cout << "建图" << endl;  
        cout << "输入顶点数 ";  
        cin >> numV;  
        cout << "边是否带权值，0(不带) or 1(带) ";  
        cin >> isWeighted;  
        cout << "是否是有向图，0(无向) or 1(有向) ";  
        cin >> isDirected;  
        Graph graph(numV, isWeighted, isDirected);  
        cout << "这是一个";  
        isDirected ? cout << "有向、" : cout << "无向、";  
        isWeighted ? cout << "有权图" << endl : cout << "无权图" << endl;  
        graph.createGraph();  
        cout << "打印邻接矩阵" << endl;  
        graph.printAdjacentMatrix();  
        cout << endl;  
        cout << "深度遍历" << endl;  
        for (int i = 0; i < numV; i++)  
        {  
            graph.dfs(i, visit);  
            cout << endl;  
        }  
        cout << endl;  
        cout << "广度遍历" << endl;  
        for (int i = 0; i < numV; i++)  
        {  
            graph.bfs(i, visit);  
            cout << endl;  
        }  
        system("pause");  
        return 0;  
    }

【代码详址】

http://blog.csdn.net/manoel/article/details/16119969

[Center]: /images/20220731/16a3563df5f140da9b91d1d56d06e3ce.png