*******************实践教学*******************兰州理工大学计算机与通信学院2012年春季学期算法与数据结构课程设计题目：图的遍历和生成树的求解实现专业班级：计算机科学与技术姓名：***学号：1234567指导教师：****成绩：目录摘要 (3)前言 (4)正文 (5)1.问题描述： (5)2.采用类C语言定义相关的数据类型 (5)3．各模块流程图及伪码算法 (6)4．函数的调用关系图 (8)5．调试分析 (9)1.调试中遇到的问题及对问题的解决方法 (9)2.算法的时间复杂度和空间复杂度 (9)6.测试结果 (10)参考文献 (14)图是一种复杂的非线性数据结构，一个图G（Grah）由两个集合V和E构成，图存在两种遍历方式，深度优先遍历和广度优先遍历，广度优先遍历基本思路是假设从图中某顶点U出发，在访问了顶点U之后依次访问U的各个未访问的领接点，然后分别从这些领接点出发依次访问他们的领接点，并使先访问的顶点的领接点先于后访问的顶点被访问。
直至所有领接点被访问到。
深度优先的基本思路是从某个顶点出发，访问此顶点，然后依次从V的未被访问的领接点出发深度优先检索土。
直至图中所有顶点都被访问到。
PRIM算法—KRUSKAL算法；可以对图形进行最小生成树的求解。
主要问题是：（1）当给出一个表达式时，如何创建图所表达的树，即相应的逻辑结构和存储结构？（2）表达式建立好以后，如何求出其遍历？深度优先和广度优先遍历。
（3）计算它的最小生成树？主要是prim算法和kruscal算法两种形式。
很多涉及图的操作的算法都是以图的遍历操作为基础，通过遍历的演示，方便在学习中更好的理解突地遍历的过程。
通过对图的深度优先遍历和广度优先遍历的演示，分别两种遍历的不同与其优缺点。
我们在对一些问题进行求解时，会发现有些问题很难找到规律，或者根本无规律可寻。
对于这样的问题，可以利用计算机运算速度快的特点，先搜索查找所有可能出现的情况，再根据题目条件从所有可能的情况中，删除那些不符合条件的解。
在深度优先搜索算法中，是深度越大的结点越先得到扩展。
如果在搜索中把算法改为按结点的层次进行搜索，本层的结点没有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是说先产生的结点先得以扩展处理，这种搜索算法称为广度优先搜索法。
很多问题都可以用广度优先搜索进行处理，如翻币问题、最短路径问题等。
在计算机中，有多种方法存储图的信息，由于图的结构复杂，使用广泛，一般应根据实际的应用，选择适合的表示方法。
常用的图的存储结构有邻接矩阵、邻接多重表和邻接表。
在实际问题当中，经常遇到这类问题，为新建的某个机构进行选址，道路交通路线，如何走完所有路线，旅游线路等一系列问题都涉及到图的知识。
图是一种复杂的非线性数据结构，一个图G（Grah）由两个集合V和E。
构成，图存在两种遍历方式，深度优先遍历和广度优先遍历，广度优先遍历基本思路是假设从图中某顶点U出发，在访问了顶点U之后依次访问U的各个未访问的领接点，然后分别从这些领接点出发依次访问他们的领接点，并使先访问的顶点的领接点先于后访问的顶点被访问。
直至所有领接点被访问到。
深度优先的基本思路是从某个顶点出发，访问此顶点，然后依次从V的未被访问的领接点出发深度优先检索图。
直至图中所有顶点都被访问到。
PRIM算法—KRUSKAL算法；可以对图形进行最小生成树的求解。
树型结构是一种非线性结构，它用于描述数据元素之间层次关系，如人类社会的族谱等，树型结构的应用非常广泛，磁盘文件目录结构就是一个典型的例子。
1.问题描述：图是一种复杂的非线性数据结构，一个图G（Grah）由两个集合V和E构成，图存在两种遍历方式，深度优先遍历和广度优先遍历，广度优先遍历基本思路是假设从图中某顶点U出发，在访问了顶点U之后依次访问U的各个未访问的领接点，然后分别从这些领接点出发依次访问他们的领接点，并使先访问的顶点的领接点先于后访问的顶点被访问。
直至所有领接点被访问到。
深度优先的基本思路是从某个顶点出发，访问此顶点，然后依次从V的未被访问的领接点出发深度优先检索土。
直至图中所有顶点都被访问到。
PRIM算法—KRUSKAL算法；可以对图形进行最小生成树的求解。
2.采用类c语言定义相关的数据类型#define int_max 10000 //定义邻接矩阵最大值10000为无穷大#define max 20 //最大顶点个数typedef struct //开始对邻接表或图进行定义{char vexs[20]; //顶点数的名称AdjMatrix arcs; //邻接矩阵int vexnum,arcnum //图中顶点数和边数int creatMGraph_L(MGraph_L &G)//创建图用邻接矩阵表示int visited[max]; //访问标记typedef struct arcnode //弧结点int adjvex; //该弧指向的顶点的位置，即边或弧依赖的顶点序号char *info; // 该弧信息char data; //结点信息基本操作：int creatadj(algraph &gra,MGraph_L G)//用邻接表存储图int initqueue(linkqueue &q)//初始化队列int enqueue(linkqueue &q,int e)//入队int dequeue(linkqueue &q,int &e)//出队int queueempty(linkqueue q)//判断队为空void bfstra(algraph gra)//广度优先遍历int bfstra_fen(algraph gra)//求连通分量3．各模块流程图及伪码算法int prim(int g[][max],int n) //最小生成树PRIM算法{int lowcost[max],prevex[max]; //LOWCOST[]存储当前集合U分别到剩余结点的最短路径//prevex[]存储最短路径在U中的结点int i,j,k,min;for(i=2;i<=n;i++) //n个顶点，n-1条边{lowcost[i]=g[1][i]; //初始化prevex[i]=1; //顶点未加入到最小生成树中}lowcost[1]=0; //标志顶点1加入U集合for(i=2;i<=n;i++) //形成n-1条边的生成树{min=inf;k=0;for(j=2;j<=n;j++) //寻找满足边的一个顶点在U,另一个顶点在V的最小边if((lowcost[j]<min)&&(lowcost[j]!=0)){min=lowcost[j];k=j;}printf("(%d,%d)%d\t",prevex[k]-1,k-1,min);lowcost[k]=0; //顶点k加入Ufor(j=2;j<=n;j++) //修改由顶点k到其他顶点边的权值if(g[k][j]<lowcost[j]){lowcost[j]=g[k][j];prevex[j]=k;}printf("\n");}return 0;}int acrvisited[100];//kruscal弧标记数组int find(int acrvisited[],int f){while(acrvisited[f]>0)f=acrvisited[f];return f;}void kruscal_arc(MGraph_L G,algraph gra) {edg edgs[20];int i,j,k=0;for(i=0;i!=G.vexnum;++i)for(j=i;j!=G.vexnum;++j){if(G.arcs[i][j].adj!=10000){edgs[k].pre=i;edgs[k].bak=j;edgs[k].weight=G.arcs[i][j].adj;++k;}}int x,y,m,n;int buf,edf;for(i=0;i!=gra.arcnum;++i)acrvisited[i]=0;for(j=0;j!=G.arcnum;++j){m=10000;for(i=0;i!=G.arcnum;++i){if(edgs[i].weight<m){m=edgs[i].weight;x=edgs[i].pre;y=edgs[i].bak;n=i;}}// cout<<x<<y<<m;// cout<<endl;buf=find(acrvisited,x);edf=find(acrvisited,y);// cout<<buf<<" "<<edf<<endl;edgs[n].weight=10000;if(buf!=edf){acrvisited[buf]=edf;cout<<"("<<x<<","<<y<<")"<<m;cout<<endl;}}}4．函数的调用关系图函数调用关系如图4.1所示图4.1 函数调用关系图5．调试分析1.调试中遇到的问题及对问题的解决方法解决Visual C++ 6.0不正确连接的问题明明改动了一个文件，却要把整个项目全部重新编译链接一次。
刚刚链接好，一运行，又提示重新编译链接一次。
这是因为出现了未来文件(修改时间和创建时间比系统时间晚)的缘故。
可以这样处理：找到工程文件夹下的debug目录，将创建和修改时间都比系统时间的文件全部删除，然后再从新“Rebuild All”一次。
2.算法的时间复杂度和空间复杂度关于时间复杂度的计算是按照运算次数来进行的, 关于空间复杂度的计算是在程序运行过程所要借助的内容空间大小。
即：空间复杂是储存空间的大小和变换等等决定的...时间复杂是逻辑比较、赋值等基本运算的次数决定的...prim算法的时间复杂度为O（n 2）,kruskcal算法的时间复杂度为O（eloge）prim的空间复杂度为O（n* prevex）, kruskcal算法的空间复杂度为O（n）6.测试结果(1）输入图的顶点即弧度个数：(2)分别写出边的权值：邻接矩阵和邻接表创建成功，显示出菜单：菜单选择：输入0，显示邻接矩阵输出y 进行下一步操作，重新选择菜单，输出1显示邻接表：输出y 进行下一步操作，重新选择菜单，输出2显示广度优先遍历：输出y 进行下一步操作，重新选择菜单，输出3显示深度优先遍历：输出y 进行下一步操作，重新选择菜单，输出4，显示prim算法计算最小生成树：输出y 进行下一步操作，重新选择菜单，输出5，显示kruscal算法计算最小生成树：输出y 进行下一步操作，重新选择菜单，输出6,计算出该图的连通分量：输出n，结束操作，退出运行:设计总结在这三周的算法与数据结构课程设计中,我的题目是:图的遍历和生成树的求解实现,这三周课程设计中,通过该题目的设计过程,我加深了对图数据结构及队列的逻辑结构,存储结构及图的深度优先和广度优先遍历过程,Prim算法和Kruscal算法进行最小生成树求解过程的理解,对图数据结构上基本运算的实现有所掌握,对课本中所学的各种数据结构进一步理解和掌握,学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的能力。