int ArrNum(Graph G,int ver)
{
    for(int i=0;i<G.VerNum;i++)
        if(G.Ver[i]==ver)
            return i;
        else
            return -1;
}

int FirstNeighbor(Graph G,int ver)
{
    int x=ArrNum(G,ver);
    for(int i=0;i<G.VerNum;i++)
    {
        if(G.Edge[x][i]==1)
            return i;
    }
    return -1;
}

int NextNeighbor(Graph G,int ver,int w)
{
    int x=ArrNum(G,ver);
    for(int i=w+1;i<G.VerNum;i++)
    {
        if(G.Edge[x][i]==1)
            return i;
    }
    return -1;
}

bool visited[MaxSize];                    //记录遍历过的结点 
void BFS(Graph G,int vnum)
{
    printf("%d ",G.Ver[vnum]);
    visited[vnum]=true;
    Queue Q;
    InitQueue(Q);
    int ver;
    int w;
    EnQueue(Q,G.Ver[vnum]);
    while(!isEmpty(Q))
    {
        DeQueue(Q,ver);
        for(w=FirstNeighbor(G,ver);w>=0;w=NextNeighbor(G,ver,w))
        {
            if(!visited[w])
            {
                printf("%d ",G.Ver[w]);
                visited[w]=true;
                EnQueue(Q,G.Ver[w]);
            }
        }
    } 
}

void BFSTraverse(Graph G)
{
    for(int i=0;i<G.VerNum;i++)
        visited[i]=false;                //将visited中元素置为false，遍历过置为true 
    for(int i=0;i<G.VerNum;i++)            //开始遍历 
    {
        if(!visited[i])
            BFS(G,i);
    }
}

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 20

typedef struct{
    int Ver[MaxSize];
    int Edge[MaxSize][MaxSize];
    int VerNum;
    int EdgeNum;
}Graph;

void CreateGraph(Graph &G)
{
    int x,i,j;
    printf("输入顶点元素:\n");
    for(i=0;i<MaxSize;i++)
    {
        scanf("%d",&x);
        if(x==-1)
            break;
        else
        {
            G.Ver[i]=x;
            G.VerNum++;    
        }
    }
    
    printf("输入边(0/1):\n");
    for(i=0;i<G.VerNum;i++)
    {
        for(j=0;j<G.VerNum;j++)
        {
            scanf("%d",&x);
            G.Edge[i][j]=x;
            if(x==1)
                G.EdgeNum++;
        }
    }
        
    G.EdgeNum=G.EdgeNum/2;
}

int ArrNum(Graph G,int ver)
{
    for(int i=0;i<G.VerNum;i++)
        if(G.Ver[i]==ver)
            return i;
        else
            return -1;
}

int FirstNeighbor(Graph G,int ver)
{
    int x=ArrNum(G,ver);
    for(int i=0;i<G.VerNum;i++)
    {
        if(G.Edge[x][i]==1)
            return i;
    }
    return -1;
}

int NextNeighbor(Graph G,int ver,int w)
{
    int x=ArrNum(G,ver);
    for(int i=w+1;i<G.VerNum;i++)
    {
        if(G.Edge[x][i]==1)
            return i;
    }
    return -1;
}

void DisplayGraph(Graph G)
{
    int i,j;
    printf("顶点元素有%d个,边有%d个\n顶点元素分别是:",G.VerNum,G.EdgeNum);
    for(i=0;i<G.VerNum;i++)
        printf("%d ",G.Ver[i]);
    printf("\n");
    printf("邻接矩阵为:\n");
    for(i=0;i<G.VerNum;i++)
        for(j=0;j<G.VerNum;j++)
        {
            printf("%d ",G.Edge[i][j]);
            if(j==G.VerNum-1)
                printf("\n");    
        }
}

typedef struct{
    int data[MaxSize];
    int front;
    int rear;
}Queue;

void InitQueue(Queue &Q)
{
    Q.front=Q.rear=0;
}

bool isEmpty(Queue Q)
{
    if(Q.front==Q.rear)    
        return true;
    return false;
}

bool isFull(Queue Q)
{
    if((Q.rear+1)%MaxSize==Q.front)
        return true;    
    return false;
}

bool EnQueue(Queue &Q,int ver)
{
    if(isFull(Q))
        return false;
    Q.data[Q.rear]=ver;
    Q.rear=(Q.rear+1)%MaxSize;
    return true;
}

bool DeQueue(Queue &Q,int &ver)
{
    if(isEmpty(Q))
        return false;
    ver=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
}

bool visited[MaxSize];                    //记录遍历过的结点 
void BFS(Graph G,int vnum)
{
    printf("%d ",G.Ver[vnum]);
    visited[vnum]=true;
    Queue Q;
    InitQueue(Q);
    int ver;
    int w;
    EnQueue(Q,G.Ver[vnum]);
    while(!isEmpty(Q))
    {
        DeQueue(Q,ver);
        for(w=FirstNeighbor(G,ver);w>=0;w=NextNeighbor(G,ver,w))
        {
            if(!visited[w])
            {
                printf("%d ",G.Ver[w]);
                visited[w]=true;
                EnQueue(Q,G.Ver[w]);
            }
        }
    } 
}

void BFSTraverse(Graph G)
{
    for(int i=0;i<G.VerNum;i++)
        visited[i]=false;                //将visited中元素置为false，遍历过置为true 
    for(int i=0;i<G.VerNum;i++)            //开始遍历 
    {
        if(!visited[i])
            BFS(G,i);
    }
}

int main()
{
    Graph G;
    CreateGraph(G);
    DisplayGraph(G);
    
    BFSTraverse(G);
    return 0;
}