动象论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 59 | 回复: 0

广度优先搜索

[复制链接]

12

主题

94

帖子

227

积分

清正廉明~版主

风纪委员

Rank: 16Rank: 16Rank: 16Rank: 16

积分
227

论坛官方最佳新人活跃会员

发表于 2020-7-18 11:37:54 | 显示全部楼层 |阅读模式
算法过程:
1.将根节点放入队列中
2.从队列中取出第一个元素,将队列中的第一个元素弹出
3.将所取得元素的全部节点加入队列中
4.判断队列是否为空
     a. 若是,则结束
     b.若不是,则跳到第二步
  1. #include <iostream>
  2. using namespace std;

  3. const int verMax=9;
  4. const int queMax=10; // >=9皆可

  5. struct node//声明图形顶点结构
  6. {
  7. int vertex;
  8. struct node *next;
  9. };

  10. typedef struct node *graph;
  11. struct node head[verMax];//声明顶点结构数组
  12. int que[queMax];
  13. int front=-1;
  14. int rear=-1;
  15. int visit[verMax];//查找记录//队列的存入

  16. int enque(int v)
  17. {
  18.     if(rear>=queMax)//队列已满
  19.     return -1;
  20. else
  21. {
  22.     rear++;//对了尾端指针后移
  23.     que[rear]=v;//将值存入队列中
  24.     return 1;
  25.     }
  26. }
  27. //队列的取出
  28. int deque()
  29. {
  30.     if(front==rear)//队列已空
  31.         return -1;
  32.     else
  33.     {
  34.         front++;
  35.         return que[front];
  36.     }
  37. }
  38. //广度优先搜索法
  39. void BFS(int v)
  40. {
  41.     graph point;
  42.     enque(v);//存入队列
  43.     visit[v]=1;//已查找
  44.     cout<<"["<<v<<"]==>";
  45.     while(front!=rear)
  46.     {
  47.         v=deque();
  48.         point=head[v].next;
  49.         while(point!=NULL)//读入邻接列表所有顶点
  50.         {
  51.             if(visit[point->vertex]==0)
  52.             {
  53.                 enque(point->vertex);//存入队列
  54.                 visit[point->vertex]=1;//已查找过的顶点
  55.                 cout<<"["<<point->vertex<<"]==>";
  56.             }
  57.             point=point->next;
  58.         }
  59.     }
  60. }
  61. //建立邻接顶点至邻接列表内
  62. void create_graph(int v1,int v2)
  63. {
  64.     graph point,New;
  65.     New=(graph)malloc(sizeof(struct node));
  66.     if(New!=NULL)
  67.     {
  68.         New->vertex=v2;//邻近顶点
  69.         New->next=NULL;
  70.         point=&(head[v1]);
  71.         while(point->next!=NULL)
  72.             point=point->next;
  73.         point->next=New;//串连在列表尾端
  74.     }
  75. }
  76. //输出邻接列表内数据
  77. void print_graph(struct node *head)
  78. {
  79.     graph point;
  80.     point=head->next;//设置point为首节点
  81.     while(point!=NULL)
  82.     {
  83.         cout<<"["<<point->vertex<<"] ";
  84.         point=point->next;
  85.     }
  86.     cout<<endl;
  87. }
  88. //主程序
  89. void main()
  90. {
  91.     int node[20][2]={
  92.     {1,2},{2,1},{1,3},{3,1},{2,4},{4,2},{2,5},{5,2},{3,6},{6,3},
  93.     {3,7},{7,3},{4,8},{8,4},{5,8},{8,5},{6,8},{8,6},{7,8},{8,7}};
  94.     int i;
  95.     for(i=0;i<verMax;i++)
  96.     {
  97.         head[i].vertex=i;
  98.         head[i].next=NULL;
  99.     }
  100.     for(i=0;i<verMax;i++)
  101.         visit[i]=0;

  102.     for(i=0;i<20;i++)
  103.         create_graph(node[i][0],node[i][1]);

  104.     cout<<"======Graph======"<<endl;
  105.     for(i=1;i<verMax;i++)
  106.     {
  107.         cout<<"Vertex["<<i<<"]: ";
  108.         print_graph(&head[i]);
  109.     }
  110.     //广度优先搜索
  111.     cout<<"Bradth-First-Search:"<<endl<<"&BEGIN==>";
  112.     BFS(4);
  113.     cout<<"END&"<<endl;
  114. }
复制代码



本帖被以下淘专辑推荐:


tel:181 5707 6602
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

 QQ 手机版小黑屋网站地图

GMT+8, 2021-8-4 01:37 Processed in 0.197615 second(s), 23 queries .

CopyRight © 2020-2021 DongXiang BBS. All Rights Reserved.

ICP备案号:粤ICP备17035028号-1

Sectigo签章 MySSL签章

快速回复 返回顶部 返回列表