图的广度优先搜索（BFS）-白红宇

把以前写过的图的广度优先搜索分享给大家（C语言版）
#include
    
     #include
     
      #define MAX_VERTEX_NUM 20#define MAXQSIZE 100#define OK 1typedef char VertexType;typedef int QElemType; typedef struct ArcNode//边结点{    int adjvex;    struct ArcNode *nextarc;}ArcNode;typedef struct VNode//定义头数组{    VertexType data;    ArcNode *firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedef struct ALGraph//定义图{    AdjList vertices;    int vernum,arcnum;}ALGraph;typedef struct SqQueue{    QElemType *base;    int front;    int rear;}SqQueue;int CreateDG(ALGraph &G){    int i,j,k,v1,v2;    ArcNode *p;    printf("请输入图的节点数：");    scanf("%d",&G.vernum );    printf("请输入图的边的个数：");    scanf("%d",&G.arcnum);    for(i=0;i
      
       G.vernum||j<1||j>G.vernum)        {            printf("请输入第%d条边的一个结点：",k+1);            scanf("%d",&v1);            printf("请输入第%d条边的一个结点：",k+1);            scanf("%d",&v2);            printf("\n");            i=v1;            j=v2;        }        p=(ArcNode *)malloc(sizeof(ArcNode));        if(!p)        {            printf("分配内存失败！\n");            return 0;        }        p->adjvex=j-1;        p->nextarc=G.vertices[i-1].firstarc;        G.vertices[i-1].firstarc=p;    }    return OK;}int InitQueue(SqQueue &Q){    Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));    if(!Q.base)    {        printf("队列内存失败！\n");        return 0;    }    Q.front=Q.rear=0;    return (OK);}int EnQueue(SqQueue &Q,QElemType e){    if((Q.rear+1)%MAXQSIZE==Q.front)    {        printf("队列已满!\n");        return 0;    }    Q.base[Q.rear]=e;    Q.rear=(Q.rear+1)%MAXQSIZE;    return (OK);}int QueueEmpty(SqQueue Q){    if(Q.front==Q.rear)        return (OK);    else         return 0;}int DeQueue(SqQueue &Q,QElemType &e){    if(Q.front==Q.rear)    {        printf("队列为空！无法删除！\n");        return 0;    }    e=Q.base[Q.front];    Q.front=(Q.front+1)%MAXQSIZE;    return (e);}void BFSTraverse(ALGraph G){    int i,j,k;    int visited[MAX_VERTEX_NUM];    ArcNode *p;    SqQueue Q;    for(i=0;i
       
        ",G.vertices[i].data);            EnQueue(Q,i);            while(!QueueEmpty(Q))            {                DeQueue(Q,j);                for(k=j,p=G.vertices[j].firstarc;p!=NULL;k=p->adjvex,p=p->nextarc)                {                    if(visited[k]==0)                    {                        visited[k]=1;                        printf("%c-->",G.vertices[k].data);                        EnQueue(Q,k);                    }                }            }        }    }}int main(){    ALGraph G;    CreateDG(G);        printf("广度优先搜索结果为\n开始-->");    BFSTraverse(G);    printf("结束!\n");    return 0;}
运行结果截图: