数据结构实验八 图的创建与遍历.doc

实验八 图的创建与遍历实验目的： 通过上机实验进一步掌握图的存储结构及基本操作的实现。实验内容与要求： 分别基于邻接矩阵和邻接表存储结构实现图的基本运算，要求： 能根据输入的顶点、边/弧的信息建立图； 实现图中顶点、边/弧的插入、删除； 实现对该图的深度优先遍历；实现对该图的广度优先遍历。源程序：#include#include#define intinity 1024#define maxvex 20typedef structchar vexmaxvex;int arcsmaxvexmaxvex;Mgraph;数组式结构体void Createmgraph(Mgraph &G,int n)创建邻接矩阵图函数，这个简单按照一般步骤就可以了int i,j; printf(请输入顶点n); for(i=1;i=n;i+)scanf(%c,&G.vexi); fflush(stdin); printf(请输入邻接矩阵(先行后列)n); for(i=1;i=n;i+) for(j=1;j=n;j+) scanf(%d,&G.arcsij); fflush(stdin); printf(创建图的邻接矩阵为n); for(i=1;i=n;i+)printf(%3c,G.vexi);这里动脑筋使他输出的界面看起来就像是一个矩阵，对位置和空格进行了调整。 printf(n);for(i=1;i=n;i+) printf(%c,G.vexi);for(j=1;j=n;j+) printf(%2d ,G.arcsij); printf(n);void Insertmgraph(Mgraph &G,int n)插入函数，这里有个缺陷，只能在尾部插入，那就简单了int i,j;printf(请输入插入的节点n);scanf(%c,&G.vexn+1);printf(请输入扩建的邻接表(先行后列)n);for(j=1;j=(n+1);j+)scanf(%d,&G.arcsn+1j); fflush(stdin);for(i=1;i(n+1);i+)scanf(%d,&G.arcsin+1); fflush(stdin);printf(输出新的图n);for(i=1;i=(n+1);i+)printf(%3c,G.vexi); printf(n);for(i=1;i=(n+1);i+) printf(%c,G.vexi);for(j=1;j=(n+1);j+) printf(%2d ,G.arcsij); printf(n);void Deleatmgraph(Mgraph &G,int n,int m)删除函数，这里不局限在哪一个点，删哪一个都可以，不过删最后对下面有好处。int i,j; printf(请输入要删除的节点n); scanf(%c,&G.vexm); for(i=m;in;i+) G.vexi=G.vexi+1; for(i=1;i=n;i+) for(j=m;jn;j+) G.arcsij=G.arcsij+1; for(j=1;jn;j+) for(i=m;in;i+) G.arcsij=G.arcsi+1j; printf(输出新的图n); for(i=1;in;i+) printf(%3c,G.vexi); printf(n); for(i=1;in;i+) printf(%c,G.vexi); for(j=1;jn;j+) printf(%2d ,G.arcsij); printf(n); void Bfstraverse(Mgraph &G,int n)广度遍历函数，由于每个函数之间都有影响所以不得不在深度函数前运行int i,j,t,k=2; char a20; a1=G.vex1;这里偷懒了，借助第二个字符数组来存储上三角矩阵信息，折掉一半简单了些，而且我还发现居然遍历的顺序就是每行元素信息的存储，比如在第一行靠前出现的必定在下一行也是靠前出现，而这个出现的会先重叠，就给函数简化了 for(i=1;i=n;i+) for(j=i;j=n;j+) if(G.arcsij!=0) ak+=G.vexj;t=k;t做记录步骤的参数，很重要for(i=1;i=t;i+)if(ai!=ai+1)控制输出就可以了，相同的不输出 printf(%c ,ai);printf(n); void Dfstraverse(Mgraph &G,int n,int i,int s)这个深度遍历可谓绞尽脑汁啊，写得想吐了，耗时一天，看书不懂，网上连类似的都找不到，我知道递归，但是要控制递归的运行，有很多条件的，即使是无向图也是很复杂的，要考虑好多种情况，感觉自己在这里都还没写全，必定还有其他情况，那就还得改条件，实在不想去想了int k,t,j=1; if(s=n) 用n作为外部递归循环的记录，否则就会是无限循环，很重要if(i=n)在大循环下考虑直线情况，循环限制数也是nprintf(%c ,G.vexi); while(G.arcsij!=1&jn)从第i行的第j个非零数开始，下次递归就到第j行去了 j+;k=j;用k做替换记录 if(G.arcsik!=0)列出非0的情况 for(t=k;t=n;t+)用for循环把对角线列元素化为0，才使得下面递归步骤判定的时候能够进行 G.arcsti=0; Dfstraverse(G,n,k,s+1);非0情况递归 Else考虑行为0的情况，也就是单个点 Dfstraverse(G,n,i+1,s+1);void main()主函数简单，就是要注意元素的加减，对下面的函数是有影响的，无影响函数我不会写int n,m; Mgraph G; printf(请输入顶点数n);scanf(%d,&n); fflush(stdin); Createmgraph(G,n); Insertmgraph(G,n); printf(请输入删除节点位置n); scanf(%d,&m); fflush(stdin); Deleatmgraph(G,n+1,m);列如在此处注意前面总数插入一个也就是加了一个printf(输出广度遍历n); Bfstraverse(G,n);printf(输出深度遍历n); Dfstraverse(G,n,1,1);printf(n);运行结果：心得体会：图是个大概念，此次我只选取了无向图，简单一点，程序的创建；插入；删除都十分简单，但是深度和广度遍历就困难了，特别是深度遍历，就像