实验4--无向图的深度优先搜索

实验4 无向图的深度优先搜索一、实验目的 1. 了解图的定义、特点，区分无向图和有向图的概念；2. 了解图的数据结构和搜索方法；3. 掌握无向图的邻接矩阵、邻接表的表示方法；4. 写出无向图的深度优先搜索程序。二、实验要求1. 了解图的定义、特点，区分无向图和有向图的概念；2. 了解图的数据结构和搜索方法；3. 掌握无向图的邻接矩阵、邻接表的表示方法；4. 写出无向图的深度优先搜索程序。三、实验内容设无向图G有n个点e条边，写一算法建立G的邻接多表，并按照深度优先搜索输出顶点，要求该算法时间复杂性为O（n+e），且除邻接多表本身所占空间之外只用O（1）辅助空间。四、实验结果1. 源代码如下：#include#include#include#include#include#define MAX_VERTEX_NUM 30#define MAX_NAME 20typedef char VertexTypeMAX_NAME;/定义边节点typedef struct EBoxbool mark;int ivex,jvex;struct EBox *ilink,*jlink;EBox;/定义顶点节点typedef struct VexBoxVertexType data;EBox *firstedge;VexBox;/定义表示图结构的结构体typedef structVexBox adjmulistMAX_VERTEX_NUM;int vexnum,edgenum;AMLGraph;/根据数据域内容返回数组下标int LocateVexBox(VertexType c,AMLGraph *g)int i;for(i=0;i(*g).vexnum;i+)if(strcmp(c,(*g).adjmulisti.data)=0)return i;return -1;/创建图的函数void CreateGraph(AMLGraph *g)int i,vi,vj;VertexType va,vb;EBox *p;printf(请输入图的顶点数：n);scanf(%d,&(*g).vexnum);printf(请输入图的边数：n);scanf(%d,&(*g).edgenum);printf(请输入图的%d个顶点：n,(*g).vexnum);for(i=0;i(*g).vexnum;i+)scanf(%s,&(*g).adjmulisti.data);(*g).adjmulisti.firstedge=NULL;printf(请输入图的%d条边,顶点之间用空格隔开：n,(*g).edgenum);for(i=0;imark=false; /将边标记为未访问vi=LocateVexBox(va,g);vj=LocateVexBox(vb,g);p-ivex=vi;p-jvex=vj;p-ilink=(*g).adjmulistvi.firstedge;(*g).adjmulistvi.firstedge=p;p-jlink=(*g).adjmulistvj.firstedge;(*g).adjmulistvj.firstedge=p;int FirstAdjvex(int i,AMLGraph *g) /获取顶点的第一条边if(iivex=i)return (*g).adjmulisti.firstedge-jvex;else return (*g).adjmulisti.firstedge-ivex;else return -1;int NextAdjvex(int i,int j,AMLGraph *g) /获取顶点i的相对于j的邻接顶点EBox *p;if(i0|jivex=i&p-jvex!=j)p=p-ilink;else if(p-jvex=i&p-ivex!=j)p=p-jlink;else break;if(p&p-ivex=i&p-jvex=j)p=p-ilink;if(p&p-ivex=i)return p-jvex;else if(p&p-jvex=i)return p-ivex;if(p&p-ivex=j&p-jvex=i)p=p-jlink;if(p&p-ivex=i)return p-jvex;else if(p&p-jvex=i)return p-ivex;return -1;int visitedMAX_VERTEX_NUM;/从下标为v的顶点出发递归的深度优先遍历图void DFS(AMLGraph *g,int v)int w;visitedv=true;printf(%s ,(*g).adjmulistv.data);for(w=FirstAdjvex(v,g);w=0;w=NextAdjvex(v,w,g)if(!visitedw)DFS(g,w);/对图作深度优先遍历void DFSTraverse(AMLGraph *g)int v;for(v=0;v(*g).vexnum;v+)visitedv=false;printf(深度遍历图的结果为：n);for(v=0;v(*g).vexnum;v+)if(!visitedv)DFS(g,v);printf(n);/该函数实现图的所有边的输出void AllEdgenum(AMLGraph *g)int v,i,j;EBox *p;for(v=0;v(*g).vexnum;v+)visitedv=false;printf(该图所有的边为：n);for(v=0;v(*g).vexnum;v+)p=(*g).adjmulistv.firstedge;while(p)if(!(*p).mark)i=(*p).ivex;j=(*p).jvex;printf(%s-%s ,(*g).adjmulisti.data,(*g).adjmulistj.data);(*p).mark=true;p=(*p).ivex=v?(*p).ilink:(*p).jlink;printf(n);void main()AMLGraph g;CreateGraph(&g);DFSTraverse(&g);AllEdgenum(&g);/测试数据/*a b c d ea bb ea dd cc eb c*/2. 运行界面截图如下：五、总结（出现的问题及解决方案或知识点总结）（不少于100字）（1）创建无向图图时，先获取顶点数与边数，再获取所有顶点的data的内容，并将其存入数组中，接下来就是创建边之间的联系了。利用循环读取边，创建边结点并给data赋值，再使该边结点的ilink和jlink分别指向其对应的顶点结点的first