图遍历的演示实习报告

1231ADT数据关系VR={(v,w)|v,wV,(v,w)vw基本操作VVRG.GG,uGG,vGvG,vGG,vG,wvG,vGG,visitvisitG,visitvisitvisit}ADT2ADT数据对象：D={ai|数据关系：R1={<ai-1,ai>|ai-S已存在。SSSe。SSeSSTRUEFALSE}ADT3ADT数据对象:D={ai|ai数据关系:R1={<ai-1,ai>|ai-1,aiai,anQQ初始条件:QTRUE,}ADT4voidmain{1#defineMAX_INFO10 /*有关信息字符串的最大长度+1*/#defineMAX_VERTEX_NUM20 /*图中顶点数的最大值*/typedefchar /*有关信息类型typedefcharVertexType; /**/typedefenum{unvisited,visited}VisitIf;typedefstruct /*访问标记 /*该边依附的两个顶点的位置structEBox /*分别指向依附这两个顶点的下一条边*/ /*该边信息指针*/typedefstruct{VertexTypedata; /*指向第一条依附该顶点的边typedefstruct{VexBox /*无向图的现在顶点数和边数intLocateVex(AMLGraphG,VertexTypeGu1VertexType&GetVex(AMLGraphG,intviintFirstAdjVex(AMLGraphG,VertexTypevG1intNextAdjVex(AMLGraphG,VertexTypev,VertexTypevwwv1voidCreateGraph(AMLGraphGStatusDeleteArc(AMLGraph&G,VertexTypev,VertexTypeG<v,w>StatusDeleteVex(AMLGraph&G,VertexTypeGvvoidDestroyGraph(AMLGraphvoidDisplay(AMLGraphGvoidDFSTraverse(AMLGraphG,VertexTypestart,（运用栈非递归）GvoidBFSTraverse(AMLGraphG,VertexTypestartGvoidMarkUnvizited(AMLGraphvoidCreateGraph(AMLGraph{/*GDestroyGraph(G);/*如果图不空,先销毁它G.edgenum；IncInfo；for(k=0;k<G.edgenum;++k)/*构造表结点链表{va、vb；i=LocateVex(G,va);/*一端*/j=LocateVex(G,vb);/**/p->mark=unvisited;/**/p-p-p->ilink=G.adjmulist[i].firstedge;/**/p->jlink=G.adjmulist[j].firstedge;/**/}}voidDisplay(AMLGraph{/*G{if(p- /*i{if(!p- /*只输出一次{}p=p-}else/*j{if(!p->mark)/*只输出一次{}p=p-}}}voidDFSTraverse(AMLGraphG,VertexType{/*startG(非递归算法 /**/{ {{ }}} /*销毁栈,释放其空间}voidBFSTraverse(AMLGraphG,VertexType /*startVisited[v]=0;/**/ /*v{ /*TRUE(*/while(!QueueEmpty(Q))/*队列不空{{}}}DestroyQueue(Q);/*销毁队列,释放其占用空间}2#defineSTACK_INIT_SIZE100/**/#defineSTACKINCREMENT10/**/typedefintSElemType;typedefstruct{ StatusInitStack(SqStack//SStatusDestroyStack(SqStack//S(无论空否均可)StatusPush(SqStack&S,SElemType//SeStatusPop(SqStack&S,SElemType//SeStatusStackEmpty(SqStack//STRUEFALSE3typedefintQelemType；typedefstructQNode{ structQNode*next;typedefstruct{QueuePtrQueuePtrrear;/*队头、队尾指针StatusInitQueue(LinkQueue//QStatusDestroyQueue(LinkQueue//Q(无论空否均可)StatusQueueEmpty(LinkQueue//Q为空队列,1,否则返回-1StatusEnQueue(LinkQueue&Q,QElemType//eQStatusDeQueue(LinkQueue&Q,QElemType//若队列不空,Q的队头元素,e返回其值,1,否则返回-14、生成树类型typedefstructCSNode{ struct /*树的二叉链表(孩子-兄弟)存储构造voidDFSTree(AMLGraphG,intv,CSTree//vG,DTvoidDFSForest(AMLGraphG,VertexTypestart,CSTree//G的深度优先生成森林的(最左)孩子(右)DTvoidPrintTraverse(CSTree//GvoidPrintAllTraverse(CSTree//GvoidBFSTree(AMLGraphG,intv,CSTree//vG,BTvoidBFSForest(AMLGraphG,VertexTypestart,CSTree//G的广度优先生成森林的(最左)孩子(右)BTvoidPrintCSTree(CSTreeT,int//用凹入表方式打印一棵以孩子-voidPrintCSForest(CSTree//用凹入表方式打印一棵以孩子-voidDFSTree(AMLGraphG,intv,CSTree /*vG,DT为根的生成树{ p- /*wv的第一种未被访问的邻接顶点是根的左孩子结点{} DFSTree(G,w,q);/*wG,}}voidBFSTree(AMLGraphG,intv,CSTree /*vG,BT为根的生成树 {{p- /*wv的第一种未被访问的邻接顶点是根的左孩子结点{} } /*回朔到上一棵生成树的根}}voidPrintCSTree(CSTreeT,int{/*用凹入表方式打印一棵以孩子-兄弟链表为存储构造的树 }voidPrintCSForest(CSTree{/*用凹入表方式打印一棵以孩子-兄弟链表为存储构造的森树for(p=T;p;p=p-{cout<<""<<i++<<"个树:"<<endl;}}5voidmain{{case1:手动构造一种图；case2:从文献导入一种图；case3:显示图的信息；case4:进行深度优先遍历图；case5:进行广度优先遍历图；case6:保存图到一种文献；case7:寻找途径；case8:销毁图；case9:退出程序；}}int /*访问标志数组(全局量)voidAllPath(AMLGraphG,VertexTypestart,VertexTypenopass,VertexTypeend,int{/*寻找途径 if(start==end)/*找到了一条简朴途径{cout<<"->"<<Path[i];/*打印输出*/}{ {AllPath(G,temp,nopass,end,k+1);/*继续寻找*/}} /*回溯}voidSaveGraph(AMLGraph /*保存图的信息{输入文献名fileName； {} /*关闭文献}voidLoadGraph(AMLGraph{fileName；{} /*关闭文献}visit(VertexType{/*输出结点*/returnOK;}void /*菜单显示{cout<<"\n\t\t********************\n"; cout<<"\t\t*******************}1、本程序以邻接多重表为存储构造。这个程序涉及到图的生成和图的深度以及广度遍历1DOS32：程序提示输入一种存有图信息文献的途径去导入一种图：4376981091）1请输入图的节点数(EG. 请输入图的边数(EG.G.edgenum=4):8个节点的表达值:FGEDCCBBAA2)3，这个图有8ABCDEFG这个图有9A-BA-B-DB-C-FC-GE-F-*****深度优先遍历图的成果ACGFBEHA-BB-DD-HH-EA-CC-FF-1ABDHECFG*****广度优先遍历图的成果ABCDEFGA-BB-DD-HB-EA-CC-FC-1ABDHEC5)7，请输入第一种结点:请输入最后一种结点:请输入您不想通过的结点:全部的途径 A结点到H结点和不想通过D结点的是A->B->E-3841，请输入图的节点数(EG.G.vexnum=10):请输入图的边数(EG