数据结构图实验报告..doc

【实验内容】 图的存储建立及遍历（DFS、BFS）： #define INFINITY 10000 #define MAX_VERTEX_NUM 40 #define MAX 40 #includestdlib.h #includestdio.h #includeconio.h #includestring.h typedef struct ArCell{ int adj; }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char name[20]; }infotype; typedef struct { infotype vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; int LocateVex(MGraph *G,char* v) { int c=-1,i; for(i=0;iG-vexnum;i++) if(strcmp(v,G-vexs[i].name)==0) {c=i;break;} return c; } MGraph * CreatUDN(MGraph *G)//初始化图，接受用户输入 { int i,j,k,w; char v1[20],v2[20]; printf(请输入图的顶点数,弧数:); scanf(%d%d,G-vexnum,G-arcnum); printf(结点名字:\n); for(i=0;iG-vexnum;i++){ printf(No.%d:,i+1); scanf(%s,G-vexs[i].name);} for(i=0;iG-vexnum;i++) for(j=0;jG-vexnum;j++) G-arcs[i][j].adj=INFINITY; printf(请输入一条边依附的两个顶点和权值:\n); for(k=0;kG-arcnum;k++) {printf(第%d条边:\n,k+1); printf(起始结点:); scanf(%s,v1); printf(结束结点:); scanf(%s,v2); printf(边的权值:); scanf(%d,w); i=LocateVex(G,v1); j=LocateVex(G,v2); if(i=0j=0){ G-arcs[i][j].adj=w; G-arcs[j][i]=G-arcs[i][j]; }} return G; } int FirstAdjVex(MGraph *G,int v) { int i; if(v=0 vG-vexnum){ //v合理 for(i=0;iG-vexnum;i++) if(G-arcs[v][i].adj!=INFINITY) return i; } return -1; } void VisitFunc(MGraph *G,int v) { printf(%s ,G-vexs[v].name); } int NextAdjVex(MGraph *G,int v,int w) { int k; if(v=0 vG-vexnum w=0 wG-vexnum)//v,w合理 { for( k=w+1;kG-vexnum;k++) if(G-arcs[v][k].adj!=INFINITY) return k; } return -1; } int visited[MAX]; void DFS(MGraph *G,int v)//从第v个顶点出发递归地深度优先遍历图G { int w; visited[v]=1; VisitFunc(G,v);//访问第v个结点 for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)) if(!visited[w]){ DFS(G,w); printf(%d ,G-arcs[v][w].adj);} } void DFSTraverse(MGraph *G,char *s)//深度优先遍历 {int v,k; for(v=0;vG-vexnum;v++) visited[v]=0; k=LocateVex(G,s); if(k=0kG-vexnum){ for(v=k;v=0;v--){ if(!visited[v]) DFS(G,v);} for(v=k+1;vG-vexnum;v++) if(!visited[v]) DFS(G,