数据结构的图的广度优先搜索实验报告--郭治民

深 圳 大 学 实 验 报 告

课程名称： 数据结构实验与课程设计

实验项目名称： 图的广度优先搜索

学院： 计算机与软件学院

专业： 计算机科学与技术

指导教师： 蔡茂国

报告人：郭治民 学号：2011150117 班级： 3

实验时间： 2012-11-05

实验报告提交时间： 2012-11-06

教务部制

一、实验目的与要求： 1、实验目的 掌握图结构的说明、创建以及图的存储表示（邻接表） 掌握队列的定义、插入、删除、清空、判空方式 掌握广度优先搜索算法原理 掌握广度优先搜索算法的编程实现方法 2、实验要求 熟悉C++语言编程 熟悉队列的操作原理 图的存储表示 熟悉广度优先搜索算法原理 熟练使用C++语言，实现广度优先搜索算法 二、实验内容： 1、问题描述 给定一个结点（始点），从它开始，对（连通）图中其它结点进行广度优先搜索。 2、图的广度优先搜索算法 所有顶点访问标志visited[]设置为FALSE,从某顶点v0开始，访问v0，visited[v0]=TRUE,将v0插入队列Q (1) 如果队列Q不空，则从队列Q头上取出一个顶点v，否则结束 (2) 依次找到顶点v的所有相邻顶点v’，如果visited[v’]=TRUE (3) 重复（1），（2） 3、输入 第一行：样本顶点个数，假设为n 第二行，n个顶点（用空格隔开） 第三行，图中边（或弧）的数目 第四行开始，每一行是边（弧）的两个顶点（用空格隔开） 4、输入样本 5、输出 广度优先搜索的顶点序列（用空格隔开，回车前无空格） 6、输出样本 三、实验步骤与过程： 1、图的定义 2、找到顶点字符在邻接表中对应的序号 3、将一个新的边插入到邻接表中 4、创建图的邻接表 5、显示邻接表 6、队列定义 7、清空队列 8、在队列中插入一个数据元素 9、在队列中删除一个数据元素 10、判断队列是否为空 11、图的广度优先搜索函数 12、主函数 代码： #include \"stdio.h\" #include \"stdlib.h\" typedef char DataType; #define MaxSize 100 #define MaxVertices 10 #define MaxEdges 100 #define MaxWeight 10000 typedef struct { DataType list[MaxSize]; int size; }SeqList; typedef struct { DataType queue[MaxSize]; int rear; int front; int count; }SeqCQueue; typedef struct { int row; int col; int weight; }RowColWeight; typedef struct { SeqList Vertices; int edge[MaxVertices][MaxVertices]; int numOfEdges; }AdjMGraph; //顺序表初始化 void ListInitiate(SeqList *L) { L->size=0; } //顺序表插入函数 int ListInsert(SeqList *L,int i,DataType x) { int j; if (L->size>=MaxSize) { printf (\"顺序表已满无法插入!\\n\"); return 0; } else if (i<0||i>L->size) { printf (\"参数i不合法!\\n\"); return 0; } else { for (j=L->size;j>i;j--) L->list[j]=L->list[j-1]; L->list[i]=x; L->size++; return 1; } } //图G初始化 void Initiate(AdjMGraph *G,int n) { int i,j; for (i=0;iedge[i][j]=0; else G->edge[i][j]=MaxWeight; } G->numOfEdges=0;//边的条数数置为0 ListInitiate(&G->Vertices);//顺序表初始化 } //在图G中插入结点vertex void InsertVertex(AdjMGraph *G,DataType vertex) { ListInsert(&G->Vertices,G->Vertices.size,vertex); } //在图G中插入边 void InsertEdge(AdjMGraph *G,int v1,int v2,int weight) { if (v1<0||v2>G->Vertices.size||v2<0||v1>G->Vertices.size) { printf (\"参数v1或v2越界出错!\\n\"); exit(1); } G->edge[v1][v2]=weight; G->numOfEdges++; } //在图G中寻找序号为v的结点的第一个邻接结点 int GetFirstVex(AdjMGraph G,int v) { int col; if (v<0||v>G.Vertices.size) { printf (\"参数v1越界出错!\\n\"); exit(1); } for (col=0;col0&&G.edge[v][col]G.Vertices.size||v2<0||v2>G.Vertices.size) { printf (\"参数v1或v2越界出错!\\n\"); exit(1); } for (col=v2+1;col0&&G.edge[v1][col]rear=0; Q->front=0; Q->count=0; } //队列非空 int QueueNotEmpty (SeqCQueue Q) { if (Q.count!=0) return 1; else return 0; } //入队列 int QueueAppend(SeqCQueue *Q,DataType x) { if((Q->rear+1)%MaxSize == Q->front) { printf(\"队列已满!\\n\"); exit(1); } Q->queue[Q->rear] =x; Q->rear = (Q->rear+1)%MaxSize; Q->count++; return 1; } //出队列 int QueueDelete(SeqCQueue *Q,DataType *x) { if(Q->front == Q->rear) { printf(\"队列是空的!\\n\"); exit(1); } *x = Q->queue[Q->front]; Q->front = (Q->front+1)%MaxSize; Q->count--; return 1; } //图的广度优先遍历函数 //连通图G以v为初始点访问操作为Visit()的广度优先遍历 //数组visited标记了相应结点是否已访问过，0表示未访问，1表示已访问 void BroadFSearch(AdjMGraph G,int v,int visited[],void Visit(DataType item)) { DataType u,w; SeqCQueue queue; Visit(G.Vertices.list[v]); visited[v]=1; QueueInitiate(&queue); QueueAppend(&queue,v); while (QueueNotEmpty(queue)) { QueueDelete(&queue,&u); w=GetFirstVex(G,u); while(w!=-1) { if (!visited[w]) { Visit(G.Vertices.list[w]); visited[w]=-1; QueueAppend(&queue,w); } w=GetNextVex(G,u,w); } } } //非连通图G访问操作为Visit()的广度优先遍历 void BroadFirstSearch(AdjMGraph G,void Visit(DataType item)) { int i; int *visited=(int *)malloc(sizeof(int)*G.Vertices.size); for (i=0;i2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。