数据结构——图的邻接矩阵的广度优先级搜索

发布时间:2017-1-19 6:11:38 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"数据结构——图的邻接矩阵的广度优先级搜索",主要涉及到数据结构——图的邻接矩阵的广度优先级搜索方面的内容,对于数据结构——图的邻接矩阵的广度优先级搜索感兴趣的同学可以参考一下。

#include <iostream> using namespace std; #define MAX_VERTEX_NUM 10 //最大顶点个数 typedef char VERTYPE; typedef struct { VERTYPE vexs[MAX_VERTEX_NUM]; //顶点向量 int visited[MAX_VERTEX_NUM]; //访问标志数组 int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和弧数 }mgraph, * MGraph; void init_mgraph(MGraph &g) //初始化图 { g=(MGraph)malloc(sizeof(mgraph)); g->vexnum=0; g->arcnum=0; for(int i=0;i<MAX_VERTEX_NUM;i++) g->vexs[i]=0; for(i=0;i<MAX_VERTEX_NUM;i++) g->visited[i]=0; //访问标志数组置0,表示没有被访问 for(i=0;i<MAX_VERTEX_NUM;i++) for(int j=0;j<MAX_VERTEX_NUM;j++) g->arcs[i][j]=0; } void add_vexs(MGraph &g) //增加顶点 { cout<<"请输入顶点的个数:"<<endl; cin>>g->vexnum; cout<<"请输入顶点的值"<<endl; for(int i=0;i<g->vexnum;i++) { cin>>g->vexs[i]; } } void add_arcs(MGraph &g) //增加边 { cout<<"请输入边的个数:"<<endl; cin>>g->arcnum; VERTYPE ch1,ch2; int row,col; for(int i=0;i<g->arcnum;i++) { cin>>ch1>>ch2; for(int j=0;j<g->vexnum;j++) { if(g->vexs[j]==ch1) { row=j; } if(g->vexs[j]==ch2) { col=j; } } g->arcs[row][col]=1; g->arcs[col][row]=1; //无向图加上此行 } } void creat_mgraph(MGraph &g) //创建图 { add_vexs(g); //增加顶点 add_arcs(g); //增加边 } void print_mgraph(MGraph &g) //打印图 { for(int i=0;i<g->vexnum;i++) cout<<" "<<g->vexs[i]; cout<<endl; for(i=0;i<g->vexnum;i++) { cout<<g->vexs[i]<<" "; for(int j=0;j<g->vexnum;j++) { cout<<g->arcs[i][j]<<" "; } cout<<endl; } } void Visit(MGraph &g,int i) { cout<<g->vexs[i]<<" "; g->visited[i]=1; } //广度优先搜索 void BFSTraverse(MGraph &g,int i) //从第i个顶点开始搜索 { int Queue[MAX_VERTEX_NUM]; //辅助队列 for(int j=0;j<MAX_VERTEX_NUM;j++) Queue[j]=0; int front=0,rear=0; //头指针和尾指针 int gettop; //取对头,它是节点的编号 Visit(g,i); Queue[rear++]=i; //入队 while(front != rear) //队列非空时 { gettop=Queue[front]; front++; //出队列 for(int j=0;j<g->vexnum;j++) if(g->arcs[gettop][j] && !g->visited[j]) { Visit(g,j); Queue[rear++]=j; //入队 } }//while } int main() { MGraph G; init_mgraph(G); //初始化图 creat_mgraph(G); //创建图 print_mgraph(G); //打印图 BFSTraverse(G,0); //广度优先搜索 return 0; }

上一篇:数据结构——深度优先搜索求点到点的一般路径
下一篇:matlab读取文件和保存文件

相关文章

相关评论