无向图的邻接表广度优先算法

向右看齐 2022-06-15 12:11 168阅读 0赞

/*无向图的邻接表广度优先算法*/
    #include<stdio.h>
    #define vnum 10
    int visited[vnum]={
       0};
    typedef struct arcnode
    {
        int adjvex;                         /*下一条边的顶点编号*/
        struct arcnode * nextarc;           /*指向下一条边的指针*/
    }ArcNode;
    typedef struct vexnode
    {
        int vertex;                         /*顶点编号*/
        ArcNode *firstarc;                  /*指向第一条边的指针*/
    }AdjList[vnum];
    typedef struct gp
    {
        AdjList adjlist;
        int vexnum,arcnum;                  /*顶点和边的个数*/
    }Graph;
    typedef int Datatype;
    typedef struct LinkQueueNode
    {
        Datatype data;                      /*数据域*/
        struct LinkQueueNode *next;         /*指向下一队列元素的指针*/
    }LkQueNode;
    typedef struct LkQueue
    {
        LkQueNode *front;                   /*前指针*/
        LkQueNode *rear;                    /*后指针*/
    }LkQue;
    /*队列初始化*/
    void InitQueue(LkQue *LQ)
    {
        LkQueNode *temp;
        temp=(LkQueNode *)malloc(sizeof(LkQueNode));    /*生成头结点*/
        LQ->front=temp;                         /*队列头指针指向队列头结点*/
        LQ->rear=temp;                          /*队列尾指针指向队列尾结点*/
        (LQ->front)->next=NULL;
    }
    /*判队列空*/
    int EmptyQueue(LkQue *LQ)
    {
        if(LQ->rear==LQ->front)
            return 1;
        else
            return 0;
    }
    /*入队列*/
    void EnQueue(LkQue *LQ,Datatype x)
    {
        LkQueNode *temp;
        temp=(LkQueNode *)malloc(sizeof(LkQueNode));
        temp->data=x;
        temp->next=NULL;
        (LQ->rear)->next=temp;                  /*新结点入队列*/
        LQ->rear=temp;                          /*置新的队列结点*/
    }
    /*出队列*/
    int OutQueue(LkQue *LQ)
    {
        LkQueNode *temp;
        if(EmptyQueue(&LQ))                     /*判队列是否为空*/
        {
            printf("队空!\n");                  /*队列为空，返回0*/
            return 0;
        }
        else                                    /*队列非空*/
        {
            temp=(LQ->front)->next;             /*使temp指向队列首结点*/
            (LQ->front)->next=temp->next;       /*修改头结点的指针域指向新的首结点*/
            if(temp->next==NULL)
                LQ->rear=LQ->front;             /*无首结点时，front和rear都指向头结点*/
            free(temp);
            return 1;
        }
    }
    /*取队列首元素*/
    Datatype Gethead(LkQue LQ)
    {
        LkQueNode *temp;
        if(EmptyQueue(&LQ))
            return 0;                        /*判队列为空，返回空数据标志。*/
        else
        {
            temp=LQ.front->next;            /*队列非空，返回队列首结点元素。*/
            return temp->data;
        }
    }
    CreateAdjlist(Graph *g,int x,int y)     /*创建并初始化邻接表*/
    {
        int i;
        g->vexnum=x;
        g->arcnum=y;
        for(i=0;i<g->vexnum;i++)
        {
            g->adjlist[i].vertex=i;         /*初始化顶点信息*/
            g->adjlist[i].firstarc=NULL;    /*初始化i的第一个邻接点为NULL*/
        }
    }
    InsertEdge(Graph *g)                    /*插入边*/
    {
        ArcNode *p;
        int i,j,k;
        for(k=0;k<g->arcnum;k++)
        {
            printf("请输入第%d条边(以空格作为间隔):",k+1);
            scanf("%d %d",&i,&j);
            p=(ArcNode *)malloc(sizeof(ArcNode));/*生成j的表结点*/
            p->adjvex=j;
            p->nextarc=g->adjlist[i].firstarc;   /*将结点j链接到i的单链表中*/
            g->adjlist[i].firstarc=p;
            p=(ArcNode *)malloc(sizeof(ArcNode));/*生成i的表结点*/
            p->adjvex=i;
            p->nextarc=g->adjlist[j].firstarc;   /*将结点i链接到j的单链表中*/
            g->adjlist[j].firstarc=p;
        }
    }
    BFS(Graph *g,int v)
    {
        LkQue Q;
        ArcNode *p;
        InitQueue(&Q);
        printf("%d ",v);
        visited[v]=1;                           /*置已访问标记*/
        EnQueue(&Q,v);                          /*访问过的顶点入队列*/
        while(!EmptyQueue(&Q))
        {
            v=Gethead(Q);
            OutQueue(&Q);                       /*顶点出队列*/
            p=g->adjlist[v].firstarc;           /*找到v的第一个邻接点*/
            while(p!=NULL)                      /*判断邻接点是否存在*/
            {
                if(!visited[p->adjvex])         /*邻接点存在未被访问*/
                {
                    printf("%d ",p->adjvex);
                    visited[p->adjvex]=1;       /*置已访问标志*/
                    EnQueue(&Q,p->adjvex);      /*邻接点入队列*/
                }
                p=p->nextarc;                   /*沿着v的邻接点链表顺序搜索*/
            }
        }
    }
    main()
    {
        Graph g;
        int i,j;
        printf("采用邻接表创建无向图G\n");
        printf("请输入图的顶点数和边数(逗号分隔):");
        scanf("%d,%d",&i,&j);
        CreateAdjlist(&g,i,j);
        InsertEdge(&g);
        printf("图G的广度优先遍历:");
        BFS(&g,0);
    }

编译效果  
![这里写图片描述][SouthEast]

[SouthEast]: /images/20220615/7ba4aa91f2204a269321a14e97506e73.png