搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 编程范 > 【优秀题解】问题 1703: 图的遍历——广度优先搜索

【优秀题解】问题 1703: 图的遍历——广度优先搜索

编程范 2018-09-07

点击蓝字

【优秀题解】问题 1703: 图的遍历——广度优先搜索

解题思路:

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指向下一个边表节点*/

           }

 

       }

 

}


(本文为我站大神“ Manchester”创作)


欢迎点击“阅读原文“”去撩原作者


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《【优秀题解】问题 1703: 图的遍历——广度优先搜索》的版权归原作者「编程范」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注编程范微信公众号

编程范微信公众号:dotcpp

编程范

手机扫描上方二维码即可关注编程范微信公众号

编程范最新文章

精品公众号随机推荐

上一篇 >>

lua数据类型