#include <iostream>

using namespace std;
const int MAXNODE=100;
int visited[MAXNODE];   //用来表示顶点是否遍历过
typedef struct SqeueNode   /*队列逻辑结构*/
{
    int data[MAXNODE];
    int *front,*rear;
}Sqeue;
typedef struct EdgeNode  /*图的边表结构*/
{
    int vertex;
    EdgeNode* next;
}EdgeNode;
typedef struct VertexNode   /*图的顶点表结构*/
{
    char data;
    EdgeNode *firstedge;
}AdjList[MAXNODE];
typedef struct MGrahp   /*以邻接表表示的图的最初结构*/
{
    AdjList adjlist;
    int numEdges,numVertexes;
}MGrahp;
void InitSqeue(Sqeue *p)    /*初始化队列*/
{
    for(int i=0;i<MAXNODE;i++)
        p->data[i]=0;
    p->front=p->data;
    p->rear=p->data;
}
void Enqueue(Sqeue *p,int a)   /*使队列元素入队*/
{
    if(p->rear-(MAXNODE-1)==p->front)
        return;
    *(p->rear)=a;
    p->rear=p->rear+1;
}
void DeQueue(Sqeue *p,int *j)   /*使队列元素出队列*/
{
    if(p->front==p->rear)
        return;
        *j=*(p->front);
    p->front=p->front+1;
}
void CreateGraph(MGrahp *G)  /*创建图的邻接表结构*/
{
    cout<<"请输入顶点的边数与顶点数:"<<endl;
    cin>>G->numEdges>>G->numVertexes;
    for(int i=0;i<G->numVertexes;i++)  /*初始化顶点表*/
    {
        cin>>G->adjlist[i].data;
        G->adjlist[i].firstedge=NULL;
    }
    for(int i=0;i<G->numEdges;i++)  /*使用头插法建立邻接表*/
    {
        cout<<"请输入边所在顶点的下标:"<<endl;
        int m,n;
        cin>>m>>n;
        EdgeNode* w=new EdgeNode;
        w->vertex=n;
        w->next=G->adjlist[m].firstedge;
        G->adjlist[m].firstedge=w;
        EdgeNode *x=new EdgeNode;
        x->vertex=m;
        x->next=G->adjlist[n].firstedge;
        G->adjlist[n].firstedge=x;
    }
}
void BFSTraverse(MGrahp *G)   /*图的广度遍历算法*/
{
    Sqeue *W=new Sqeue;
    EdgeNode *p;
    for(int i=0;i<G->numVertexes;i++)   /*初始化visited，表示没有遍历过任何一个点*/
       visited[i]=0;
       InitSqeue(W);
       for(int i=0;i<G->numVertexes;i++) /*宽度遍历主循环*/
       {
           if(visited[i]==1)           /*若顶点被遍历过，返回*/
            return;
          visited[i]=1;
          cout<<G->adjlist[i].data<<endl;  /*开端*/
          Enqueue(W,i);
          int* x=new int;
          while(W->front!=W->rear)   /*队列不为空时*/
          {
              DeQueue(W,x);        /*出队列*/
              p=G->adjlist[*x].firstedge;  /*将上面出队列的顶点的邻接点找到，并标示访问过，并让其入队列*/
              while(p)
              {
                  if(visited[p->vertex]==0)
                  {
                      visited[p->vertex]=1;
                     cout<<G->adjlist[p->vertex].data<<endl;
                    Enqueue(W,p->vertex);
                  }
                  p=p->next;
              }

          }
       }
}
int main()
{
    MGrahp *G=new MGrahp;
    CreateGraph(G);   /*创建图*/
    BFSTraverse(G);    /*进行图的广度遍历*/
    return 0;

样例.png

样例结果.png

图的广度遍历流程图

图的广度遍历.png

图的广度遍历1.png

疑问

代码中的队列有神马作用呢？

解答

假如没有队列的话，会出现什么情况呢？第一个结点入队列后，只能找到当前结点的子结点。而子结点的子结点会很难找，而且难以保证遍历的次序。而如果有了队列，让父节点出队列，让父节点的子结点入队列，保证了遍历的顺序。