图的广度优先搜索（BFS）

把以前写过的图的广度优先搜索分享给大家（C语言版）
#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 20
#define MAXQSIZE 100
#define OK 1
typedef 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;i++)
    {
        printf("请输入第%d个顶点数据：",i+1);
        getchar();
        scanf("%c",&G.vertices[i].data);
        //G.vertices[i].data=i;
        G.vertices[i].firstarc=NULL;
    }
    printf("请输入节点的边关系，如：结点1和结点2有边就输入1和2（每条边就输入一次）：\n");
    for(k=0;k<G.arcnum;k++)
    {
        printf("请输入第%d条边的一个结点：",k+1);
        scanf("%d",&v1);
        printf("请输入第%d条边的另一个结点：",k+1);
        scanf("%d",&v2);
        printf("\n");
        i=v1;
        j=v2;
        while(i<1||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.vernum;i++)
        visited[i]=0;
    InitQueue(Q);
    for(i=0;i<G.vernum;i++)
    {
        if(visited[i]==0)
        {
            visited[i]=1;
            printf("%c-->",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;
}
运行结果截图:
相关文章：
