#include <iostream>

using namespace std;
const int MAXNODE=100;
int visited[MAXNODE];   //用來表示頂點是否遍歷過
typedef struct SqeueNode   /*隊列邏輯結(jié)構(gòu)*/
{
    int data[MAXNODE];
    int *front,*rear;
}Sqeue;
typedef struct EdgeNode  /*圖的邊表結(jié)構(gòu)*/
{
    int vertex;
    EdgeNode* next;
}EdgeNode;
typedef struct VertexNode   /*圖的頂點表結(jié)構(gòu)*/
{
    char data;
    EdgeNode *firstedge;
}AdjList[MAXNODE];
typedef struct MGrahp   /*以鄰接表表示的圖的最初結(jié)構(gòu)*/
{
    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)  /*創(chuàng)建圖的鄰接表結(jié)構(gòu)*/
{
    cout<<"請輸入頂點的邊數(shù)與頂點數(shù):"<<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++) /*寬度遍歷主循環(huán)*/
       {
           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);   /*創(chuàng)建圖*/
    BFSTraverse(G);    /*進行圖的廣度遍歷*/
    return 0;

樣例.png

樣例結(jié)果.png

圖的廣度遍歷流程圖

圖的廣度遍歷.png

圖的廣度遍歷1.png

疑問

代碼中的隊列有神馬作用呢踢步？

解答

假如沒有隊列的話，會出現(xiàn)什么情況呢丑掺？第一個結(jié)點入隊列后获印，只能找到當前結(jié)點的子結(jié)點。而子結(jié)點的子結(jié)點會很難找街州，而且難以保證遍歷的次序兼丰。而如果有了隊列，讓父節(jié)點出隊列唆缴，讓父節(jié)點的子結(jié)點入隊列鳍征，保證了遍歷的順序。