首页 广度优先算法

广度优先算法

举报
开通vip

广度优先算法广度优先算法 #include #include typedef struct arc_node /*表节点 代表着弧或边*/ { int adjvex; /*与弧相关联的另一个节点的编号*/ struct arc_node *next_arc; /*下一个同弧尾的弧*/ }arc_node; typedef struct /*头节点*/ { char data; /*顶点数据*/ arc_node *first_arc; /*以此顶点为弧尾的第一个弧(表节点)的指针*/ }vnode,adj...

广度优先算法
广度优先算法 #include #include typedef struct arc_node /* 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 节点 代表着弧或边*/ { int adjvex; /*与弧相关联的另一个节点的编号*/ struct arc_node *next_arc; /*下一个同弧尾的弧*/ }arc_node; typedef struct /*头节点*/ { char data; /*顶点数据*/ arc_node *first_arc; /*以此顶点为弧尾的第一个弧(表节点)的指针*/ }vnode,adj_list[20]; typedef struct { adj_list vertices; int vnum,arcnum; int kind; }Graph; void create_graph(Graph *g) { FILE *fp; int i,j; char a,b; int m,n; arc_node *p; fp=fopen("mygraph.txt","rt"); if(fp==NULL)return ; fscanf(fp,"%d\n",&g->vnum); fscanf(fp,"%d\n",&g->arcnum); for(i=0;ivnum;i++) { fscanf(fp,"%c\n",&(g->vertices[i].data)); g->vertices[i].first_arc=NULL; } for(i=0;iarcnum;i++) { fscanf(fp,"%c",&a); fscanf(fp,"%c\n",&b); m=locate(g,a); n=locate(g,b); if(m<0||n<0)return; p=(arc_node *)malloc(sizeof(arc_node)); /*此处建立的是无向图*/ p->adjvex=n; /*每一条边对应存储结构中的*/ p->next_arc=g->vertices[m].first_arc; /*两个表节点*/ g->vertices[m].first_arc=p; p=(arc_node *)malloc(sizeof(arc_node)); /*所以分别在编号m,n的顶点*/ p->adjvex=m; /*后加链*/ p->next_arc=g->vertices[n].first_arc; g->vertices[n].first_arc=p; } fclose(fp); } int locate(Graph *g,char c) { int i; for(i=0;ivnum;i++) { if(g->vertices[i].data==c)return i; } return -1; } int visited[20]; /*全局数组用于标记顶点是否曾经访问*/ /*与在邻接矩阵存储方式下的深度优先搜索相比,只有下面两个函数不同*/ int first_adjvex(Graph g,int v) /*寻找图g顶点向量中与编号*/ { /*为v的顶点关联的第一个节点的编号*/ arc_node *p=g.vertices[v].first_arc; if(p!=NULL) return p->adjvex; return -1; } int next_adjvex(Graph g,int v,int w) { arc_node *p=g.vertices[v].first_arc; while(p!=NULL&&p->adjvex!=w) { p=p->next_arc; } if(p!=NULL&&p->next_arc!=NULL)return p->next_arc->adjvex; return -1; } void BFS_traverse(Graph g) { int i,j,w; int queue[20]; int rear=0,front=0; /*定义队列*/ for(i=0;i=0;j=next_adjvex(g,w,j)) { if(visited[j]==0) { printf("%c ",g.vertices[j]); visited[j]=1; queue[rear]=j; rear=(rear+1)%20; } }/*for*/ }/*while*/ }/*if*/ } } main() { Graph g; create_graph(&g); BFS_traverse(g); getch(); }
本文档为【广度优先算法】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_321635
暂无简介~
格式:doc
大小:18KB
软件:Word
页数:0
分类:生活休闲
上传时间:2017-10-07
浏览量:21