Contents

#include <stdio.h>
#include <stdlib.h>
#include <queue>
using namespace std;

#define MAXVEX 100                      //最大顶点数,应由用户定义
#define INFINITY 65535                  //用65535来代表∞

bool visited[MAXVEX];                    //访问标志数组
typedef char VertexType;                //顶点类型应用户定义
typedef int  EdgeType;                  //边上的权值应由用户定义
typedef int InforType;                  //信息的类型由用户定义

typedef struct EdgeNode                //边表结点
{
    int adjvex;                        //邻接点域,存储该顶点对应的下标
    EdgeType weight;                   //用于存储权值,对于非网图可以不需要
    struct EdgeNode *next;             //链域,指向下一个邻接点
}EdgeNode;

typedef struct VertexNode              //顶点表结点
{
    VertexType data;                   //顶点域,存储顶点信息
    EdgeNode *firstedge;               //边表头指针  建立边表
}VertexNode;

typedef struct GraphAdjlist
{
    VertexNode adjlist[MAXVEX];        //建立顶点表
    int numVertex, numEdge;            //图中当前顶点数和边数
}GraphList;

//邻接矩阵的广度遍历算法
void BFSTraverse(GraphList g){

    int i, j;
    EdgeNode * p;
    queue <int> q;
    for(i = 0; i < g.numVertex; i++)
        visited[i] = false;
    for(i = 0; i < g.numVertex; i++)
    {
        if(!visited[i])
        {
            visited[i] = true;
            printf("%c ", g.adjlist[i].data);   //打印顶点，也可以其他操作
            q.push(i);               //将这个点入队
            while(!q.empty())
            {
                int m = q.front();
                q.pop();
                p = g.adjlist[m].firstedge;
                while(p)
                {
                    if(!visited[p->adjvex])
                    {
                        visited[p->adjvex] = true;
                        printf("%c ", g.adjlist[p->adjvex].data);
                        q.push(p->adjvex);
                    }
                    p = p->next;
                }
            }
        }
    }
}