图的遍历和生成树求解实现的课程结构设计

*******************实践教学*******************兰州理工大学计算机与通信学院2012年春季学期算法与数据结构课程设计题目：______________专业班级：_______________姓名：_______________学号：指导教师：李睿成绩：_______________目录摘要 (2)1．采用类C语言定义相关数据类型 (2)2．各模块流程图及伪码算法 (3)3．函数的调用关系图 (10)4．调试分析 (11)5．测试结果 (12)6.源程序（见附录） (18)设计总结 (19)参考文献 (20)致谢 (20)附件Ⅰ任务一源程序代码 (21)摘要很多涉及图上操作的算法都是以图的遍历操作为基础的，该设计要求写一个程序，演示出图遍历的过程，并给出图的生成树（网的最小代价生成树）。

通过该题目的设计过程，可以加深理解图数据结构及队列的逻辑结构、存储结构及图的深度优先和广度优先遍历过程，掌握图数据据结构上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养动手能力。

关键字：图；深度优先遍历；广度优先遍历；生成树1．采用类C语言定义相关数据类型图存储结构的定义：1）顺序存储（邻接矩阵）#define MAX_VERTEX_NUM 30 //最大顶点个数Typedef enum{DG,DN,UDG,UDN} GraphKind; //图的种类：有向图、有向网、无向图、无向网ArcTypeAdjMtrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //ArcType 是顶点关系类型，对无权图，用0和1表示是否相邻，对于网，则为权值类型typedef struct {VertexType vex[MAX_VERTEX_NUM]; //顶点数组AdjMtrix arc; //邻接矩阵int vexnum,arcnum; //图中的顶点数和边数GraphKind kind; //图的种类}GraphMtrix;（2）邻接表的存储#define MAX_VERTEX_NUM 30 //最大顶点个数typedef struct EdgeNode{ //表结点int adjvex; //边或弧依赖的顶点序号InfType *info; //弧或边的相关信息，在网中则为权值struct EdgeNode *next;}EdgeNode;typedef struct VexNode{ //顶点元素VertexType vextex;EdgeNode *link;}VexNode,AdjList[MAX_VERTEX_NUM];typedef struct{ //邻接表AdjList vertices;int vexnum,arcnum; //图中的顶点数和边数GraphKind kind; //图的种类} AdjListGrap2．各模块流程图及伪码算法(1) 遍历算法a.深度优先遍历void DFS(AdjListGraph G,int v)//图G采用邻接表存储结构，v是遍历起始点在邻接表中的下标值，其下标从0开始{visited[v]=1; //置已访问标志visite(G.vertices[v].vextex); //访问顶点for (p = G.vertices[v].link; p; p = p->next)if (!visited[p->adjvex])DFS(G,p->adjvex);//当前顶点未访问，继续深度优先遍历} // DFSb.广度优先遍历void BFS(AdjListGrap G,intv)//图G采用邻接表存储结构，v是遍历起始点在邻接表中的下标，邻接表中下标从0开始，以队列作为基本辅助数据结构{InitQueue(Q); //初始化队列Qvisited[v]=1; //置已访问标志visite(G.vertices[v]. vextex); //访问顶点EnQueue(Q,v); //被访问顶点入队while (!QueueEmpty(Q)){DeQueue(Q,v); //出队列for (p = G.vertices[v].link; p; p = p->next) //找所有和v相邻接的顶点if (!visited[p->adjvex]){visited[p->adjvex]=1;visite(G.vertices [p->adjvex].vextex);EnQueue(Q,p->adjvex);} //if} //while} // BFS(2)流程图a.深度优先遍历dfstrab.广度优先遍历Bfstrac.Prim算法(3) 程序的伪代码算法：a.广度优先遍历：void dfstra (MGraph *G，int i){ /*以vi为出发点对邻接矩阵表示的图G进行DFS搜索，设邻接矩阵是0,l矩阵*/整型 j；打印 ("visit vertex：％c"，G->vexs[i])；/*访问顶点vi*/ visited[i]=TRUE；for(j=0；j<G->n；j++) /*依次搜索vi的邻接点*/if(G->edges[i][j]==1&&!visited[j])DFSM(G，j)/*(vi ，vj)∈E，且vj未访问过，故vj为新出发点}DFSM*/说明：对于具有n个顶点和e条边的无向图或有向图，遍历算法DFSTraverse对图中每顶点至多调用一次DFS或DFSM。

摘要图(Gｒaph)是一种复杂的非线性结构。

图可以分为无向图、有向图。

若将图的每条边都赋上一个权，则称这种带权图网络。

在人工智能、工程、数学、物理、化学、计算机科学等领域中，图结构有着广泛的应用。

在图结构中，对结点（图中常称为顶点)的前趋和后继个数都是不加以限制的,即结点之间的关系是任意的。

图中任意两个结点之间都可能相关。

图有两种常用的存储表示方法:邻接矩阵表示法和邻接表表示法。

在一个图中，邻接矩阵表示是唯一的，但邻接表表示不唯一。

在表示的过程中还可以实现图的遍历（深度优先遍历和广度优先遍历）及求图中顶点的度。

当然对于图的广度优先遍历还利用了队列的五种基本运算(置空队列、进队、出队、取队头元素、判队空)来实现。

这不仅让我们巩固了之前学的队列的基本操作，还懂得了将算法相互融合和运用。

目录第一章课程设计目的..................................................................................... 错误!未定义书签。

第二章课程设计内容和要求....................................................................... 错误!未定义书签。

2．1课程设计内容.................................................................................. 错误!未定义书签。

2.1.1图的邻接矩阵的建立与输出ﻩ错误!未定义书签。

2．１.２图的邻接表的建立与输出............................................... 错误!未定义书签。

2.1.3图的遍历的实现.................................................................... 错误!未定义书签。

数据结构与算法课程设计报告课程设计题目：图的算法实现专业班级：信息与计算科学1002班目录摘要 (1)1、引言 (1)2、需求分析 (1)3、概要设计 (2)4、详细设计 (4)5、程序设计 (10)6、运行结果 (18)7、总结体会 (19)摘要(题目): 图的算法实现实验内容图的算法实现问题描述：（1）将图的信息建立文件；（2）从文件读入图的信息，建立邻接矩阵和邻接表；（3）实现Prim、Kruskal、Dijkstra和拓扑排序算法。

关键字:邻接矩阵、Dijkstra和拓扑排序算法1.引言本次数据结构课程设计共完成图的存储结构的建立、Prim、Kruskal、Dijkstra 和拓扑排序算法等问题。

通过本次课程设计，可以巩固和加深对数据结构的理解，通过上机和程序调试，加深对课本知识的理解和熟练实践操作。

（1）通过本课程的学习，能够熟练掌握数据结构中图的几种基本操作；（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。

使用语言：CPrim算法思想：从连通网N={V,E}中的某一顶点v0出发，选择与它关联的具有最小权值的边(v0,v)，将其顶点加入到生成树的顶点集合V中。

以后每一步从一个顶点在V中，而另一个顶点不在V中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合V中。

如此继续下去，直到网中的所有顶点都加入到生成树顶点集合V中为止。

拓扑排序算法思想：1、从有向图中选取一个没有前驱的顶点，并输出之；2、从有向图中删去此顶点以及所有以它为尾的弧；重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。

没有前驱-- 入度为零，删除顶点及以它为尾的弧-- 弧头顶点的入度减1。

2.需求分析1、通过键盘输入建立一个新的有向带权图，建立相应的文件；2、对建立的有向带权图进行处理，要求具有如下功能：（1）用邻接矩阵和邻接表的存储结构输出该有向带权图，并生成相应的输出结果；（2）用Prim、Kruskal算法实现对图的最小生成树的求解，并输出相应的输出结果；（3）用Dijkstra算法实现对图中从某个源点到其余各顶点的最短路径的求解，并输出相应的输出结果；（4）实现该图的拓扑排序算法。

实验三图的遍历生成树
实验项目：图的遍历生成树
实验类型: 验证性
实验目的：
1.熟悉图结构
2.掌握图结构上的各种操作
3.学会运用图结构求解问题
涉及的知识点：图的表示法、生成树的概念、图的深度优先、广度优先遍历算法，拓扑排序、最短路径和关键路径
实验内容：
编写程序实现对下图的先深、先广遍历
具体要求：
1. 使用图的邻接矩阵表示法进行编程
2. 实现如下基本接口
FirstAdj(v): 找到编号为v的顶点的第一个邻接顶点
NextAdj(v,w): 设w是v的邻接顶点, 找到v的排在w后的下一个邻接顶点. DepthFirstSearch(v) 对连通图从顶点v开始进行深度优先访问
BreadthFirstSearch(v) 对连通图从顶点v开始进行广度优先访问
实验报告的书写：
实验原理：编写源程序的方法、依据
实验过程原始记录：打印与自己编写的源代码关键的程序段，附加注解
实验结果及分析：打印屏幕输入、输出结果。

注意：除了从顶点1出发之外，再选择另一个结点，即打印两组测试数据（均使用上面指定输入的图）。

数据结构图的遍历实验报告篇一：【数据结构】图的存储和遍历实验报告《数据结构B》实验报告系计算机与电子专业级班姓名学号XX年1 0 月9日1. 上机题目：图的存储和遍历2. 详细设计#include#define GRAPHMAX 10#define FALSE 0#define TRUE 1#define error printf#define QueueSize 30typedef struct{char vexs[GRAPHMAX];int edges[GRAPHMAX][GRAPHMAX];int n,e;}MGraph;int visited[10];typedef struct{int front,rear,count;int data[QueueSize];}CirQueue;void InitQueue(CirQueue *Q) {Q->front=Q->rear=0;Q->count=0;}int QueueEmpty(CirQueue *Q){return Q->count=QueueSize;}int QueueFull(CirQueue *Q){return Q->count==QueueSize;}void EnQueue(CirQueue *Q,int x) { if(QueueFull(Q)) error("Queue overflow");文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持else{ Q->count++;Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%QueueSize;}}int DeQueue(CirQueue *Q){int temp;if(QueueEmpty(Q)){ error("Queue underflow");return NULL;}else{ temp=Q->data[Q->front]; Q->count--;Q->front=(Q->front+1)%QueueSize;return temp;}}void CreateMGraph(MGraph *G){int i,j,k;char ch1,ch2;printf("\n\t\t 请输入定点数，边数并按回车 (格式如：3，4)：");scanf("%d,%d", &(G->n),&(G->e));for(i=0;in;i++){ getchar();printf("\n\t\t 请输入第%d个定点数并按回车：",i+1);scanf("%c",&(G->vexs[i]));}for(i=0;in;i++)for(j=0;jn;j++)G->edges[i][j]=0;for(k=0;ke;k++){ getchar();printf("\n\t\t 请输入第%d条边的顶点序号 (格式如：i,j )：",k+1);scanf("%c,%c",&ch1,&ch2);for(i=0;ch1!=G->vexs[i];i++);for(j=0;ch2!=G->vexs[j];j++);G->edges[i][j]=1;}}void DFSM(MGraph *G,int i){int j;printf("\n\t\t 深 度 优 列： %c\n",G->vexs[i]);visited[i]=TRUE;for(j=0;jn;j++)if(G->edges[i][j]==1 &&////////////////DFSM(G,j);} void BFSM(MGraph *G,int k){ int i,j;CirQueue Q;InitQueue(&Q);printf("\n\t\t 广 度 优列： %c\n",G->vexs[k]);visited[k]=TRUE;EnQueue(&Q,k); while(!QueueEmpty(&Q)){ i=DeQueue(&Q);先遍历序 visited[j]!=1)先遍历序for(j=0;jn;j++)if(G->edges[i][j]==1 && visited[j]!=1) { visited[j]=TRUE;EnQueue(&Q,j);}}}void DFSTraverseM(MGraph *G) {int i;for(i=0;in;i++)visited[i]=FALSE;for(i=0;in;i++)if(!visited[i]) DFSM(G,i);}void BFSTraverseM(MGraph *G) {int i;for(i=0;in;i++) visited[i]=FALSE;for(i=0;in;i++)if(!visited[i]) BFSM(G,i);}void main(){MGraph *G,a;char ch1;int i,j,ch2;G=&a;printf("\n\t\t 建立一个有向图的邻接矩阵表示\n"); CreateMGraph(G);printf("\n\t\t 已建立一个有向图的邻接矩阵存储\n"); for(i=0;in;i++){ printf("\n\t\t");for(j=0;jn;j++)printf("%5d",G->edges[i][j]);}getchar();ch1='y';while(ch1=='y'||ch1=='Y'){ printf("\n");printf("\n\t\t 图的存储与遍历");("\n\t\t** ******************************");printf("\n\t\t*1 ---- 更新邻接矩阵*"); printf("\n\t\t*2 ---- 深度优先遍历*"); printf("\n\t\t*3 ---- 广度优先遍历*"); printf("\n\t\t*0 ---- 退出*");printf("\n\t\t** ******************************");}} printf("\n\t\t 请选择菜单号 ( 0 ---------------- 3) "); scanf("%d",&ch2); getchar(); switch(ch2) { case1:CreateMGraph(G); printf("\n\t\t 图的邻接矩阵存储建立完成\n");break; case 2:DFSTraverseM(G);break; case3:BFSTraverseM(G);break; case 0:ch1='n';break;default:printf("\n\t\t 输出错误！清重新输入！"); }3. 调试分析（1）调试过程中主要遇到哪些问题？是如何解决的？由于实习之初对邻接表的存储结构了解不是很清楚，所以在运行出了一个小错误，即在输出邻接表时，每个结点都少了一个邻接点。

数据结构教案第七章图第7章图【学习目标】1．领会图的类型定义。

2．熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。

3．熟练掌握图的两种遍历算法。

4．理解各种图的应用问题的算法.【重点和难点】图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。

【知识点】图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径【学习指南】离散数学中的图论是专门研究图性质的一个数学分支，但图论注重研究图的纯数学性质，而数据结构中对图的讨论则侧重于在计算机中如何表示图以及如何实现图的操作和应用等.图是较线性表和树更为复杂的数据结构,因此和线性表、树不同，虽然在遍历图的同时可以对顶点或弧进行各种操作，但更多图的应用问题如求最小生成树和最短路径等在图论的研究中都早已有了特定算法，在本章中主要是介绍它们在计算机中的具体实现。

这些算法乍一看都比较难，应多对照具体图例的存储结构进行学习。

而图遍历的两种搜索路径和树遍历的两种搜索路径极为相似，应将两者的算法对照学习以便提高学习的效益。

【课前思考】1。

你有没有发现现在的十字路口的交通灯已从过去的一对改为三对，即每个方向的直行、左拐和右拐能否通行都有相应的交通灯指明。

你能否对某个丁字路口的6条通路画出和第一章绪论中介绍的”五叉路口交通管理示意图”相类似的图？2。

如果每次让三条路同时通行，那么从图看出哪些路可以同时通行？同时可通行的路为：（AB，BC,CA)，（AB,BC,BA),(AB，AC,CA)，（CB,CA,BC）目录第7章图 (1)7.1图的定义和基本术语 (1)7.2图的存储和创建 (2)7.2.1 图的存储表示 (2)7。

2.2 图的创建 (5)7。

3图的遍历 (5)7。

3.1 深度优先搜索 (5)7.3.2 广度优先搜索 (6)7。

4遍历算法的应用 (8)7.4。

课程设计报告课程名称数据结构课题名称图的遍历专业网络工程班级学号姓名指导教师陈淑红、张晓清、黄哲2015年 6 月25 日湖南工程学院课程设计任务书课程名称数据结构课题图的遍历专业班级网络工程学生姓名学号指导老师陈淑红、张晓清、黄哲审批任务书下达日期2015 年 3 月 1 日任务完成日期2015 年6月25 日目录一、设计内容与设计要求 (2)1.1设计内容---------------------------------------------------------------------------------------2 1.2选题方案---------------------------------------------------------------------------------------2 1.3设计要求---------------------------------------------------------------------------------------21.4进度安排---------------------------------------------------------------------------------------5二、需求分析 (5)2.1程序功能---------------------------------------------------------------------------------------52.2输入输出要求---------------------------------------------------------------------------------5三、概要设计 (5)3.1流程图------------------------------------------------------------------------------------------5 3.2数据结构---------------------------------------------------------------------------------------63.3函数的调用关系图，主要函数的流程---------------------------------------------------9四、详细设计 (14)4.1定义图------------------------------------------------------------------------------------------14 4.2自动生成无向图------------------------------------------------------------------------------14 4.3手动生成无向图------------------------------------------------------------------------------16 4.4广度优先遍历---------------------------------------------------------------------------------174.5深度优先遍历---------------------------------------------------------------------------------20五、调试运行 (22)5.1 测试数据--------------------------------------------------------------------------------------22 5.2运行程序---------------------------------------------------------------------------------------22 5.3自动生成图操作------------------------------------------------------------------------------235.4手动生成图操作------------------------------------------------------------------------------26六、心得体会 (29)七、源代码 (29)八、评分表 (38)第一章设计内容与设计要求1.1设计内容1.1.1 算术24游戏演示由系统随机生成4张扑克牌，用户利用扑克牌的数字及运算符号“+”、“—”、“*”、“/”及括号“（”和“）”从键盘上输入一个计算表达式，系统运行后得出计算结果，如果结果等于24，则显示“Congratulation!”，否则显示“Incorrect!”设计思路：从键盘输入中缀表达式，然后将中缀表达式转换为后缀表达式，利用后缀表达式求值。