• / 26
  • 下载费用:19 金币  

图的广度遍历课程设计报告

关 键 词:
广度 遍历 课程设计 报告
资源描述:
目 录1.需求分析11.1 问题描述 11.2 系统功能 12.概要设计22.1 流程图22.2 结构体、函数及说明 33.详细设计43.1 遍历函数设计 43.2 容错性方法设计 43.3 生成邻接表设计 53.4 邻接表遍历设计 64.程序源代码75.调试分析和测试结果.165.1 调试分析 .165.1 调试案例 .165.3 测试过程、结果截图: .175.3.1 容错性测试: .175.3.2 无向图(案例一)测试: .205.3.3 有向图(案例二)测试: .226.课程设计总结.24参考文献.2501.需求分析1.1 问题描述 (1)对任意给定的图(顶点数和边数自定),建立它的邻接表并输出。(2)然后利用队列的五种基本运算(置空队列、进队、出队、取队头元素、判队空)实现图的广度优先搜索遍历。(3)画出搜索顺序示意图。1.2 系统功能(1)首先输入图的类型,有向或无向图(因为遍历与权值无关,所以没有涉及带权图)。然后输入图的顶点数、边数和各条边,之后生成该图的邻接表并输出。(2)再输入要遍历该图的起点,然后从所输入的点广度搜索该图的邻接表,并按遍历顺序输出顶点内容。之后决定是否继续遍历该图或输入另一个需要遍历的图亦或是结束程序。12.概要设计2.1 流程图是否否是图 2-1 流程图开始输入图的类型确定图的类型输入有向图输入无向图广度优先遍历该图输入从哪个顶点开始遍历该图是否从其他顶点开始重新遍历该图结束是否结束22.2 结构体、函数及说明typedef struct ArcNode//邻接表表结点{int adjvex;//该弧所指向的顶点位置struct ArcNode *nextarc;//指向下一条弧的指针//InfoType *info;//该弧相关信息指针}ArcNode;typedef struct VNode//邻接表头结点{VertexType data;//结点信息ArcNode *firstarc;//指向第一条依附该结点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedef struct//图{AdjList Vertices;//邻接表头结点数组int vexnum,arcnum;//图的当前顶点数和弧数int kind;//图的种类标志(有向图:0,无向图:1)}ALGraph;void print(int v)//输出顶点信息int FirstAdjVex(ALGraph G,int u)//在邻接表 G 中取第 u 个头结点void NextAdjVex(ALGraph G,int u,int w)// 在邻接表 G 中取第 u 个头结点之后的结点 w 的下一结点void BFSTraverse(ALGraph G,queue Q,bool visited[],int m,int n,void (*Visit)(int))//使用辅助队列 Q 从邻接表结点 m 开始 n 结束广度遍历邻接表图 G33.详细设计3.1 遍历函数设计void BFSTraverse(ALGraph G,queue Q,bool visited[],int m,int n,void (*Visit)(int))//使用辅助队列 Q 从邻接表结点 m 开始 n 结束广度遍历邻接表图 G{ //按广度优先非递归遍历图 G。使用辅助队列 Q 和访问标志数组 visited。while(!Q.empty()) Q.pop();//置空的辅助队列 Qfor(int v=m;v= 0; w = NextAdjVex(G,u,w))//从以 u 为头结点的邻接表开始遍历到链表中的最后一个结点if(!visited[w])//w 为 u 的尚未访问的邻接结点{visited[w]=true;Visit(w);//访问 wQ.push(w);//w 入队列}//if}//while}//if}//BFSTraverse*/3.2 容错性方法设计coutn||tG.vexnum||tG.vexnum||nadjvex = n2;//结点赋值为 n25G.Vertices[n1].firstarc->nextarc= NULL;//设置 n2 之后的结点为空}else//如果 n1 后已有结点{ArcNode *p = G.Vertices[n1].firstarc;//新建结点指针while((p->nextarc)!=NULL)p = p->nextarc;//将指针指向链表中最后一个结点p->nextarc = new ArcNode;//在最后增加一个新结点p->nextarc->adjvex = n2;//给结点赋值 n2p->nextarc->nextarc=NULL; //设置 n2 之后的结点为空}}3.4 邻接表遍历设计coutG.vexnum||t Q;//定义辅助队列 Qfor(int j=0;j#include #define MAX_VERTEX_NUM 101#define VertexType intusing namespace std;typedef struct ArcNode//邻接表表顶点{int adjvex;//该弧所指向的顶点位置struct ArcNode *nextarc;//指向下一条弧的指针//InfoType *info;//该弧相关信息指针}ArcNode;typedef struct VNode//邻接表头顶点{VertexType data;//顶点信息ArcNode *firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedef struct//图{AdjList Vertices;//邻接表头顶点数组int vexnum,arcnum;//图的当前顶点数和弧数int kind;//图的种类标志(有向图:0,无向图:1)}ALGraph;void print(int v)//输出顶点信息{coutadjvex;}int NextAdjVex(ALGraph G,int u,int w)// 在邻接表 G 中取第 u 个头顶点之后的顶点 w 的下一顶点{ArcNode *p = G.Vertices[u].firstarc;while(w != p->adjvex)p = p->nextarc;if(p->nextarc==NULL)return -1;return p->nextarc->adjvex;}void BFSTraverse(ALGraph G,queue Q,bool visited[],int m,int n,void (*Visit)(int))//使用辅助队列 Q 从邻接表顶点 m 开始 n 结束广度遍历邻接表图 G{//按广度优先非递归遍历图 G。使用辅助队列 Q 和访问标志数组 visited。while(!Q.empty()) Q.pop();//置空的辅助队列 Qfor(int v=m;v= 0; w = NextAdjVex(G,u,w))if(!visited[w])//w 为 u 的尚未访问的邻接顶点8{visited[w]=true;Visit(w);Q.push(w);}//if}//while}//if}//BFSTraverse*/int main(){int t,n;char s[10],c[10];ALGraph G;do{system(“cls“);cout99||tn||tG.vexnum||tG.vexnum||nadjvex = n2;G.Vertices[n1].firstarc->nextarc= NULL;}else{ArcNode *p = G.Vertices[n1].firstarc;while((p->nextarc)!=NULL)p = p->nextarc;p->nextarc = new ArcNode;p->nextarc->adjvex = n2;p->nextarc->nextarc=NULL;}}}else{11coutn||tG.vexnum||tG.vexnum||nadjvex = n2;G.Vertices[n1].firstarc->nextarc= NULL;}else{ArcNode *p = G.Vertices[n1].firstarc;while((p->nextarc)!=NULL)p = p->nextarc;p->nextarc = new ArcNode;p->nextarc->adjvex = n2;p->nextarc->nextarc=NULL;}if(!visited[n2]){visited[n2]=true;G.Vertices[n2].firstarc = new ArcNode;G.Vertices[n2].firstarc->adjvex = n1;G.Vertices[n2].firstarc->nextarc= NULL;}else{ArcNode *p = G.Vertices[n2].firstarc;while((p->nextarc)!=NULL)p = p->nextarc;p->nextarc = new ArcNode;p->nextarc->adjvex = n1;p->nextarc->nextarc=NULL;}}}do{cout“adjvex+1;p = p->nextarc;}coutG.vexnum||t Q;for(int j=0;j
展开阅读全文
  麦档网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:图的广度遍历课程设计报告
链接地址:https://www.maidoc.com/p-6376828.html

当前资源信息

李振财

编号: 20180805220717251786

类型: 共享资源

格式: DOC

大小: 768.35KB

上传时间: 2018-08-13

关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

[email protected] 2018-2020 maidoc.com版权所有  文库上传用户QQ群:3303921 

麦档网为“文档C2C模式”,即用户上传的文档所得金币直接给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的金币归上传人(含作者)所有。
备案号:蜀ICP备17040478号-3  
川公网安备:51019002001290号 

本站提供办公文档学习资料考试资料文档下载


收起
展开