图的广度优先遍历实现

图的广度优先遍历，除了本身存储顶点和邻边的信息需要存储空间外，还需要借助一个队列，空间复杂度是O(1)～O(Vertex)

其实这个遍历算法跟树的层次遍历很类似，也是加多了个visited[] 数组标记是否已经访问过，避免死循环的情况

直接上代码

#include 
#include 
#include 
#include 

using namespace std;


#define MAX_NUM 20                   //顶点的最大个数


typedef struct {
    int Vex[MAX_NUM];
    int Edge[MAX_NUM][MAX_NUM];
    int vexnum;
}Graph;


typedef struct linkNode{
    int data;//顶点数组下标
    struct linkNode *next;
} linkNode;
// 整个队列我们需要2个指针，队头指针，队尾指针
typedef struct linkQueue{
    linkNode *front, *rear;
} linkQueue;

bool visited[MAX_NUM];
//队列begin

// 带头结点初始化
void init_queue(linkQueue &Q){
    Q.front = Q.rear = (linkNode *)malloc(sizeof(linkNode));
    Q.front->next = NULL;
}

// 入队
bool enter_queue(linkQueue &Q, int value){
    linkNode *p = (linkNode *)malloc(sizeof(linkNode));
    // 内存不够，分配失败
    if (p == NULL) {
        return false;
    }
    // 构建好p结点数据
    p->data = value;
    p->next = NULL;
    
    // 入队
    Q.rear->next = p;
    
    // 队尾指针永远指向最后一个元素
    Q.rear = p;
    return true;
}

// value 是一个指针，一个TNode类型的指针，另外需要修改指针本身的值，而不是修改指针指向的地址的值，所以要加引用
bool del_queue(linkQueue &Q, int &value){
    if (Q.front == Q.rear) {
        return false;
    }
    linkNode *p = Q.front->next;
    value = p->data;
    Q.front->next = p->next;
    
    // 如果是最后一个数据元素，修改尾指针
    if (p == Q.rear) {
        Q.rear = Q.front;
    }
    free(p);
    return true;
}
//队列end



int FirstNeighbor(Graph g, int x){
    for (int i = 1; i<=g.vexnum; i++) {
        if (g.Edge[x][i]>0) {
            return g.Vex[i];
        }
    }
    return -1;
}

int NextNeighbor(Graph g, int x, int y){
    for (int i = y+1; i<=g.vexnum; i++) {
        if (g.Edge[x][i]>0) {
            return g.Vex[i];
        }
    }
    return -1;
}

void BFS(Graph g, int v);
void BFSTraverse(Graph g){
    for (int i = 1; i<=g.vexnum; i++) {
        visited[i] = false;
    }
    for (int i = 1; i<=g.vexnum; i++) {
        if (!visited[i]) {
            BFS(g, i);
        }
    }
}
void BFS(Graph g, int v){
    linkQueue Q;
    init_queue(Q);
    enter_queue(Q, v);
    visited[v] = true;
    int w = 0, u = 0;
    while (Q.front->next!=NULL) {
        del_queue(Q, u);
        cout << "elements:" << u << endl;
        for (w = FirstNeighbor(g, u); w>0; w = NextNeighbor(g, u, w)) {
            if (!visited[w]) {
                visited[w] = true;
                enter_queue(Q, w);
            }
        }
    }
}

int main(){
    cout << "welcome, to my world!" < 
输出
 
welcome, to my world!
 size of :1684
 elements:1
 elements:2
 elements:3
 elements:4
 elements:5
 Program ended with exit code: 0