Manchester- 图的遍历——广度优先搜索

解题思路:
1):为了这里代码把输入的邻接矩阵转化为了邻接表，之后再进行BFS。

2):广度优先遍历相当于树的层次遍历：选取图中任意一个顶点开始遍历，然遍历该节点的所有未被访问的边表节点，再把访问了的边表节点入队列，出队列一个节点，循环上述过程，直到队列为空。

①：选取图中任意顶点v开始遍历（题目选取为编号为0）

②：先访问v顶点，让后再把v入队列

③：若队列不为空循环下面部分

  1）：出队列一个节点

  2）：让p指向他的第一个边表节点

  3）：若p不为空，循环遍历v的所有没有被访问的边表节点，访问后把被访问节点入队列
④：队列空结束遍历

邻接矩阵转化为邻接表实现代码：

void creat_adjlist(agraph G,int n)
{
    G->n=n;/*保存顶点数*/
    /*建立邻接表的顶点表*/
    G->adjlist=(vnode)malloc(n*sizeof(VNode));

    /*下面分别建立边表节点*/
    int b;/*保存邻接矩阵中的0，1*/

    ArcNode Head;/*为边表节点建立头节点*/
    Head.nextarc=NULL;

    arcnode p=&Head;/*让p指向头节点*/
    arcnode q;
    /*创建邻接表*/
    for(int i=0;i<n;i++)
    {    /*一定要单独建立每一个顶点的边表*/
        /*每次建立完一个边表后，初始化*/
        Head.nextarc=NULL;
        p=&Head;

        for(int j=0;j<n;j++)
      {
        scanf("%d",&b);
        if(b==1)/*顶点i到顶点j之间有边，则建立边表节点j*/
        {   /*创建边表节点*/
            q=(arcnode)malloc(sizeof(ArcNode));
            q->adjvex=j;/*保存该边表节点编号*/

            /*后插入节点*/
            p->nextarc=q;
            q->nextarc=NULL;
            p=q;
        }
      }
      /*最后把该边表加入邻接表中对应顶点节点后*/
      G->adjlist[i].firstarc=Head.nextarc;
    }
}

注意：每个顶点的边表单独建立，也就是每次建立时要初始化，否则不正确；

参考代码:

#include<stdio.h>
#include<malloc.h>

typedef struct ArcNode_{
 int adjvex;
 struct ArcNode_ *nextarc;

}*arcnode,ArcNode;

typedef struct VNode_{
 char data;
 ArcNode * firstarc;

}*vnode,VNode;

typedef struct Agraph_{
 VNode *adjlist;
 int n,e;

}*agraph,Agraph;

void BFS_(Agraph *G,int v,int *visit);

void creat_adjlist(agraph G,int n);
/*=================================================*/
int main()
{
    int n;

    while(scanf("%d",&n)!=EOF)
    {
        Agraph G;
        creat_adjlist(&G,n);
        int visit[n];/*定义访问数组*/
        for(int i=0;i<n;i++)
            visit[i]=0;

        BFS_(&G,0,visit);
        printf("\n");/*行尾换行*/
    }
    return 0;
}
/*===============================================*/
void creat_adjlist(agraph G,int n)
{
    G->n=n;/*保存顶点数*/
    /*建立邻接表的顶点表*/
    G->adjlist=(vnode)malloc(n*sizeof(VNode));

    /*下面分别建立边表节点*/
    int b;/*保存邻接矩阵中的0，1*/

    ArcNode Head;/*为边表节点建立头节点*/
    Head.nextarc=NULL;

    arcnode p=&Head;/*让p指向头节点*/
    arcnode q;
    /*创建邻接表*/
    for(int i=0;i<n;i++)
    {    /*一定要单独建立每一个顶点的边表*/
        /*每次建立完一个边表后，初始化*/
        Head.nextarc=NULL;
        p=&Head;

        for(int j=0;j<n;j++)
      {
        scanf("%d",&b);
        if(b==1)/*顶点i到顶点j之间有边，则建立边表节点j*/
        {   /*创建边表节点*/
            q=(arcnode)malloc(sizeof(ArcNode));
            q->adjvex=j;/*保存该边表节点编号*/

            /*后插入节点*/
            p->nextarc=q;
            q->nextarc=NULL;
            p=q;
        }
      }
      /*最后把该边表加入邻接表中对应顶点节点后*/
      G->adjlist[i].firstarc=Head.nextarc;
    }
}
/*===============================================*/
void BFS_(Agraph *G,int v,int *visit)
{
    int que[G->n];/*建立队列*/
    int front=0,rear=0;

     /*输出当前遍历到的节点编号*/
     printf("%d ",v);
     visit[v]=1;/*编号为v的节点设置为已访问*/

     /*把该节点入队列*/
     rear=(rear+1)%G->n;
     que[rear]=v;

     int J;
     ArcNode *p;/*定义一个边表节点指针，下面遍历边表节点使用*/
       while(front!=rear)
       {
           /*队列节点出队列*/
           front=(front+1)%G->n;
           J=que[front];

           p=G->adjlist[J].firstarc;
           /*开始遍历边表节点*/
           while(p!=NULL)
           {
               if(visit[p->adjvex]==0)/*如果该p->adjvex编号所指节点没有被访问*/
               {
                   /*访问且输出该节点编号*/
                   printf("%d ",p->adjvex);
                   visit[p->adjvex]=1;
                   /*把该节点入队列*/
                    rear=(rear+1)%G->n;
                    que[rear]=p->adjvex;
               }
               p=p->nextarc;/*p指向下一个边表节点*/
           }

       }

}

别忘点赞哦-.-