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

深 圳 大 学 实 验 报 告 课程名称： 数据结构实验与课程设计 实验项目名称： 图的广度优先搜索 学院： 计算机与软件学院 专业： 计算机科学与技术 指导教师： 蔡茂国 报告人：郭治民 学号：2011150117 班级： 3 实验时间： 2012-11-05 实验报告提交时间： 2012-11-06 教务部制一、实验目的与要求：1、实验目的 掌握图结构的说明、创建以及图的存储表示（邻接表） 掌握队列的定义、插入、删除、清空、判空方式 掌握广度优先搜索算法原理 掌握广度优先搜索算法的编程实现方法2、实验要求 熟悉C+语言编程熟悉队列的操作原理图的存储表示熟悉广度优先搜索算法原理熟练使用C+语言，实现广度优先搜索算法二、实验内容：1、问题描述 给定一个结点（始点），从它开始，对（连通）图中其它结点进行广度优先搜索。2、图的广度优先搜索算法 所有顶点访问标志visited设置为FALSE,从某顶点v0开始，访问v0，visitedv0=TRUE,将v0插入队列Q(1) 如果队列Q不空，则从队列Q头上取出一个顶点v，否则结束(2) 依次找到顶点v的所有相邻顶点v，如果visitedv=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.htypedef char DataType;#define MaxSize 100#define MaxVertices 10#define MaxEdges 100#define MaxWeight 10000typedef struct DataType listMaxSize; int size;SeqList;typedef struct DataType queueMaxSize; int rear; int front; int count;SeqCQueue;typedef struct int row; int col; int weight;RowColWeight;typedef struct SeqList Vertices; int edgeMaxVerticesMaxVertices; 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 (iL-size) printf (参数i不合法!n); return 0; else for (j=L-size;ji;j-) L-listj=L-listj-1; L-listi=x; L-size+; return 1; /图G初始化void Initiate(AdjMGraph *G,int n) int i,j; for (i=0;in;i+) for (j=0;jedgeij=0; else G-edgeij=MaxWeight; G-numOfEdges=0;/边的条数数置为0 ListInitiate(&G-Vertices);/顺序表初始化/在图G中插入结点vertexvoid InsertVertex(AdjMGraph *G,DataType vertex) ListInsert(&G-Vertices,G-Vertices.size,vertex);/在图G中插入边void InsertEdge(AdjMGraph *G,int v1,int v2,int weight) if (v1G-Vertices.size|v2G-Vertices.size) printf (参数v1或v2越界出错!n); exit(1); G-edgev1v2=weight; G-numOfEdges+;/在图G中寻找序号为v的结点的第一个邻接结点int GetFirstVex(AdjMGraph G,int v) int col; if (vG.Vertices.size) printf (参数v1越界出错!n); exit(1); for (col=0;col0&G.edgevcolMaxWeight) return col; return -1;/在图G中寻找v1结点的邻接结点v2的下一个邻接结点int GetNextVex(AdjMGraph G,int v1,int v2) int col; if (v1G.Vertices.size|v2G.Vertices.size) printf (参数v1或v2越界出错!n); exit(1); for (col=v2+1;col0&G.edgev1colMaxWeight) return col; return -1;/在图G中插入n个结点信息V和e条边信息E(创图函数)void CreatGraph(AdjMGraph *G,DataType V,int n,RowColWeight E,int e) int i,k; Initiate(G,n); for (i=0;in;i+) InsertVertex(G,Vi); for (k=0;krear=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-queueQ-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-queueQ-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.listv); visitedv=1; QueueInitiate(&queue); QueueAppend(&queue,v); while (QueueNotEmpty(queue) QueueDelete(&queue,&u); w=GetFirstVex(G,u); while(w!=-1) if (!visitedw) Visit(G.Vertices.listw); visitedw=-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;iG.Vertices.size;i+) visitedi=0; for(i=0;iG.Vertices.size;i+) if (!visitedi) BroadFSearch(G,i,visited,Visit); free(visited);/定义访问操作的函数void Visit(DataType item) printf ( %c ,item);/主函数void main(void) AdjMGraph g1; DataType a=1,2,3,4,5;/图的结点 RowColWeight rcw=0,1,1,0,2,1,0,3,1,0,4,1,1,0,1,1,3,1,2,0,1,2,4,1,3,0,1,3,1,1,4,0,1,4,2,1; int n=5,e=12; int i,j; CreatGraph(&g1,a,n,rcw,e);/创图函数 printf (结点集合为: n); for (i=0;ig1.Vertices.size;i+) printf ( %c ,g1.Vertices.listi); printf (n); printf (n); printf (权值集合为: n); for (i=0;ig1.Vertices.size;i+) for (j=0;jg1.Vertices.size;j+) printf (%5d ,g1.edgeij); printf (n); printf (n广度优先搜索序列为:n); BroadFirstSearch(g1,Visit); printf (n);四、实验结果及数据处理分析： 1、结果截图2、结果分析 因为输入样本和