队列+图的BFS（严书风格代码）

在上一篇文章中，我详细介绍了图的存储结构，以及实现了DFS的操作，在这篇文章中，我来完成下BFS。（可以先自己尝试写一写再来和我的代码进行对比下，因为我也不能保证我写的是对的hhh）

BFS的原理我就不多赘述了，网上的各种博客网课比我肯定比我讲的好得多，先去看看原理流程再看代码会简单很多。

首先来实现下循环队列的基本操作：

此队列参考了王道P74页中间部分：区分是队空还是队满的情况，有三种处理方式中的第三种。

typedef struct Queue {
    int data[MaxVertexNum];
    int front, rear, tag;
} Queue;

bool EnQueue(Queue & que, int p) { //将p入队
    if(que.rear == que.front && que.tag == 1) {
        cout << "Queue is full!" << endl;
        return false;
    }

    que.data[que.rear] = p;
    que.rear = (que.rear + 1) % MaxVertexNum;
    que.tag = 1;
    return true; 
}

bool DeQueue(Queue & que, int & p) { //将对头元素出队，并且赋值给p返回
    if(que.front == que.rear && que.tag == 0) {
        cout << "Queue is empty!" << endl;
        return false;
    }

    p = que.data[que.front];
    que.front = (que.front + 1) % MaxVertexNum;
    que.tag = 0;
    return true;
}

BFS的实现，队列中存放的是节点的编号：

void BFS(ALGraph G, int i) {
    cout << G.vertices[i].data << endl;  //输出第一个结点
    visited[i] = true;  //标记为访问过

    Queue que;
    que.front = que.rear = que.tag = 0; //这里一定要初始化，我之前因为忘记初始化导致调bug调了半个多小时。。
    EnQueue(que, i); 

    while(!(que.front == que.rear && que.tag == 0)) { //若队列非空
        int p;
        DeQueue(que, p);
        //将p有关系的结点加入队列中
        ArcNode * cur = G.vertices[p].first;  //准备访问相邻结点
        while(cur) {
            if(!visited[cur -> adjvex]) {
                cout << G.vertices[cur -> adjvex].data << endl;
                EnQueue(que, cur -> adjvex);
                visited[cur -> adjvex] = true;
            }
            cur = cur -> next;
        }
    }        
}

void BFSTraverse(ALGraph G) {
    for(int i = 0; i < G.vertexnum; ++i) {
        visited[i] = false;
    }

    for(int i = 0; i < G.vertexnum; ++i) {
        if(!visited[i])
            BFS(G, i);
    }
}

完整代码：

#include<iostream>
#include<queue>
using namespace std;

#define MaxVertexNum 100
#define VertexType char

//边表结点
typedef struct ArcNode { 
    int adjvex;          //存储该结点在顶点表中的下标
    ArcNode * next;      //指向下一个边表
}ArcNode;

//顶点表结点
typedef struct VNode {  
    VertexType data;            //顶点信息
    ArcNode * first;             //指向边表
} VNode, AdjList[MaxVertexNum]; //顶点和顶点表

//图的存储结构
typedef struct {       
    AdjList vertices;  //邻接表
    int vertexnum, arcnum; //维护图的顶点数和边的个数
} ALGraph;

//队列：
typedef struct Queue {
    int data[MaxVertexNum];
    int front, rear, tag;
} Queue;

bool EnQueue(Queue & que, int p) {
    if(que.rear == que.front && que.tag == 1) {
        cout << "Queue is full!" << endl;
        return false;
    }

    que.data[que.rear] = p;
    que.rear = (que.rear + 1) % MaxVertexNum;
    que.tag = 1;
    return true; 
}

bool DeQueue(Queue & que, int & p) {
    if(que.front == que.rear && que.tag == 0) {
        cout << "Queue is empty!" << endl;
        return false;
    }

    p = que.data[que.front];
    que.front = (que.front + 1) % MaxVertexNum;
    que.tag = 0;
    return true;
}
//找到结点x在顶点表中的位置
int LocateVex(ALGraph & G, VertexType x) {
    for(int i = 0; i < G.vertexnum; i ++) {
        if(x == G.vertices[i].data) 
            return i;
    }
    return -1;
}

void CreateALGrapha(ALGraph & G) {
    //cout << "输入顶点数和边数：";
    cin >> G.vertexnum >> G.arcnum;
    for(int i = 0; i < G.vertexnum; ++i) {
        //cout << "输入第" << i + 1 << "个顶点的信息：";
        cin >> G.vertices[i].data;
        G.vertices[i].first = NULL;
    }

    for(int i = 0; i < G.arcnum; ++i) {
        VertexType e1, e2;
        //cout << "输入第" << i + 1 << "条边的顶点：";
        cin >> e1 >> e2;
        ArcNode * e = new ArcNode;
        if(!e) {
            cout << "内存分配失败：" << endl;
            exit(0);
        }

        
        int vi = LocateVex(G, e1);
        int vj = LocateVex(G, e2);

        //e1和e2之间有一条边，先用头插法将e2的边表插到e1的顶点表后
        e -> adjvex = vj;
        e -> next = G.vertices[vi].first;
        G.vertices[vi].first = e;

         if(!e) {
            cout << "内存分配失败：" << endl;
            exit(0);
        }

        //再将e1的边表插到e2的顶点表
        e -> adjvex = vi;
        e -> next = G.vertices[vj].first;
        G.vertices[vj].first = e;
    }
}

bool visited[MaxVertexNum];
void BFS(ALGraph G, int i) {
    cout << G.vertices[i].data << endl;
    visited[i] = true;

    Queue que;
    que.front = que.rear = que.tag = 0; 
    EnQueue(que, i); 

    while(!(que.front == que.rear && que.tag == 0)) { //若队列非空
        int p;
        DeQueue(que, p);
        //将p有关系的结点加入队列中
        ArcNode * cur = G.vertices[p].first;
        while(cur) {
            if(!visited[cur -> adjvex]) {
                cout << G.vertices[cur -> adjvex].data << endl;
                EnQueue(que, cur -> adjvex);
                visited[cur -> adjvex] = true;
            }
            cur = cur -> next;
        }
    }  
      
}

void BFSTraverse(ALGraph G) {
    for(int i = 0; i < G.vertexnum; ++i) {
        visited[i] = false;
    }

    for(int i = 0; i < G.vertexnum; ++i) {
        if(!visited[i])
            BFS(G, i);
    }
}

int main() {
    ALGraph G;
    CreateALGrapha(G);
    cout << "BFS：" << endl;
    BFSTraverse(G);
}

/*
5 7
a b c d e
a b
a e
b c
b d
b e
c d
d e
*/

结尾彩蛋：学长说的没错，考研期间coding真的很爽hhh