图的广度优先搜索(BFS)

把以前写过的图的广度优先搜索分享给大家(C语言版)

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #define MAX_VERTEX_NUM 20
  4 #define MAXQSIZE 100
  5 #define OK 1
  6 typedef char VertexType;
  7 typedef int QElemType;
  8  
  9 typedef struct ArcNode//边结点
 10 {
 11     int adjvex;
 12     struct ArcNode *nextarc;
 13 }ArcNode;
 14 
 15 typedef struct VNode//定义头数组
 16 {
 17     VertexType data;
 18     ArcNode *firstarc;
 19 }VNode,AdjList[MAX_VERTEX_NUM];
 20 
 21 typedef struct ALGraph//定义图
 22 {
 23     AdjList vertices;
 24     int vernum,arcnum;
 25 }ALGraph;
 26 
 27 typedef struct SqQueue
 28 {
 29     QElemType *base;
 30     int front;
 31     int rear;
 32 }SqQueue;
 33 
 34 int CreateDG(ALGraph &G)
 35 {
 36     int i,j,k,v1,v2;
 37     ArcNode *p;
 38     printf("请输入图的节点数:");
 39     scanf("%d",&G.vernum );
 40     printf("请输入图的边的个数:");
 41     scanf("%d",&G.arcnum);
 42     for(i=0;i<G.vernum;i++)
 43     {
 44         printf("请输入第%d个顶点数据:",i+1);
 45         getchar();
 46         scanf("%c",&G.vertices[i].data);
 47         //G.vertices[i].data=i;
 48         G.vertices[i].firstarc=NULL;
 49     }
 50     printf("请输入节点的边关系,如:结点1和结点2有边就输入1和2(每条边就输入一次):\n");
 51     for(k=0;k<G.arcnum;k++)
 52     {
 53         printf("请输入第%d条边的一个结点:",k+1);
 54         scanf("%d",&v1);
 55         printf("请输入第%d条边的另一个结点:",k+1);
 56         scanf("%d",&v2);
 57         printf("\n");
 58         i=v1;
 59         j=v2;
 60         while(i<1||i>G.vernum||j<1||j>G.vernum)
 61         {
 62             printf("请输入第%d条边的一个结点:",k+1);
 63             scanf("%d",&v1);
 64             printf("请输入第%d条边的一个结点:",k+1);
 65             scanf("%d",&v2);
 66             printf("\n");
 67             i=v1;
 68             j=v2;
 69         }
 70         p=(ArcNode *)malloc(sizeof(ArcNode));
 71         if(!p)
 72         {
 73             printf("分配内存失败!\n");
 74             return 0;
 75         }
 76         p->adjvex=j-1;
 77         p->nextarc=G.vertices[i-1].firstarc;
 78         G.vertices[i-1].firstarc=p;
 79     }
 80     return OK;
 81 }
 82 int InitQueue(SqQueue &Q)
 83 {
 84     Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));
 85     if(!Q.base)
 86     {
 87         printf("队列内存失败!\n");
 88         return 0;
 89     }
 90     Q.front=Q.rear=0;
 91     return (OK);
 92 }
 93 
 94 int EnQueue(SqQueue &Q,QElemType e)
 95 {
 96     if((Q.rear+1)%MAXQSIZE==Q.front)
 97     {
 98         printf("队列已满!\n");
 99         return 0;
100     }
101     Q.base[Q.rear]=e;
102     Q.rear=(Q.rear+1)%MAXQSIZE;
103     return (OK);
104 }
105 int QueueEmpty(SqQueue Q)
106 {
107     if(Q.front==Q.rear)
108         return (OK);
109     else 
110         return 0;
111 }
112 
113 int DeQueue(SqQueue &Q,QElemType &e)
114 {
115     if(Q.front==Q.rear)
116     {
117         printf("队列为空!无法删除!\n");
118         return 0;
119     }
120     e=Q.base[Q.front];
121     Q.front=(Q.front+1)%MAXQSIZE;
122     return (e);
123 }
124 void BFSTraverse(ALGraph G)
125 {
126     int i,j,k;
127     int visited[MAX_VERTEX_NUM];
128     ArcNode *p;
129     SqQueue Q;
130     for(i=0;i<G.vernum;i++)
131         visited[i]=0;
132     InitQueue(Q);
133     for(i=0;i<G.vernum;i++)
134     {
135         if(visited[i]==0)
136         {
137             visited[i]=1;
138             printf("%c-->",G.vertices[i].data);
139             EnQueue(Q,i);
140             while(!QueueEmpty(Q))
141             {
142                 DeQueue(Q,j);
143                 for(k=j,p=G.vertices[j].firstarc;p!=NULL;k=p->adjvex,p=p->nextarc)
144                 {
145                     if(visited[k]==0)
146                     {
147                         visited[k]=1;
148                         printf("%c-->",G.vertices[k].data);
149                         EnQueue(Q,k);
150                     }
151                 }
152             }
153         }
154     }
155 }
156 int main()
157 {
158     ALGraph G;
159     CreateDG(G);
160     
161     printf("广度优先搜索结果为\n开始-->");
162     BFSTraverse(G);
163     printf("结束!\n");
164     return 0;
165 }

运行结果截图:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏菩提树下的杨过

base64编码在silverlight中的使用

在传统的.net应用中,使用base64编码字符串是一件很轻松的事情,比如下面这段代码演示了如何将本地文件转化为base64字符串,并且将base64字符串又还...

23370
来自专栏函数式编程语言及工具

Akka(8): 分布式运算:Remoting-远程查找式

  Akka是一种消息驱动运算模式,它实现跨JVM程序运算的方式是通过能跨JVM的消息系统来调动分布在不同JVM上ActorSystem中的Actor进行运算,...

44790
来自专栏猿人谷

du熊学斐波那契I

du熊学斐波那契I Time Limit : 2000/1000ms (C/Other)   Memory Limit : 65535/32768K (C/Ot...

194100
来自专栏刘君君

JDK8的ConcurrentHashMap源码学习笔记

46140
来自专栏恰童鞋骚年

Hadoop学习笔记—12.MapReduce中的常见算法

    "数据去重"主要是为了掌握和利用并行化思想来对数据进行有意义的筛选。统计大数据集上的数据种类个数、从网站日志中计算访问地等这些看似庞杂的任务都会涉及数据...

15720
来自专栏xingoo, 一个梦想做发明家的程序员

文件上传---动作条

  利用Apache commons fileupload上传文件,直接显示其完成的进度条。----示例代码源自《JAVA WEB王者归来》   1 首先要显示...

26380
来自专栏小樱的经验随笔

HDU 2438 Turn the corner(三分查找)

托一个学弟的福,学了一下他的最简便三分写法,然后找了一道三分的题验证了下,AC了一题,写法确实方便,还是我太弱了,漫漫AC路!各路大神,以后你们有啥好的简便写法...

30150
来自专栏码匠的流水账

聊聊rocketmq的PushConsumerImpl

io/openmessaging/rocketmq/consumer/PushConsumerImpl.java

20020
来自专栏lgp20151222

SSH上一个随笔的基础上添加上hibernate支持

熟悉的pom.xml其中lo4g和slf4j这两个包第一眼看上去有点莫名奇妙,我也是这么觉得的,实际作用是在后台输出sql语句,不导入hibernate就会报错...

8910
来自专栏Java 技术分享

Ajax 案例之三级联动

36060

扫码关注云+社区

领取腾讯云代金券