实验三编写算法,依次输入顶点的数目、弧的数目、个顶点信息和各条弧的信息建立有向图的邻接表(已通过vc6.0)

1、#include#include#defineTrue1#defineFalse0#defineMAX_VERTEX_NUM20/*最多顶点个数*/intvisitedMAX_VERTEX_NUM;/*访问标志数组*/typedefenumDG,DN,UDG,UDNGraphKind;/*图的种类*/typedefcharVertexData;typedefstructArcNodeintadjvex;/*该弧指向顶点的位置*/structArcNode*nextarc;/*指向下一条弧的指针*/ArcNode;typedefstructVertexNodeVertexDatadata;/*顶

2、点数据*/ArcNode*firstarc;/*指向该顶点第一条弧的指针*/VertexNode;typedefstructVertexNodevertexMAX_VERTEX_NUM;intvexnum,arcnum;/*图的顶点数和弧数*/GraphKindkind;/*图的种类标志*/AdjList;/*基于邻接表的图(AdjacencyListGraph)*/intLocateVertex(AdjList*G,charv)/*求顶点位置函数*/intj=-1,k;for(k=0;kvexnum;k+)if(G-vertexk.data=v)j=k;break;return(j);voi

3、dCreateAdjList(AdjList*G)/*创建一个有向网*/inti,j,k,m;VertexDatav1,v2;ArcNode*s;ArcNode*p;printf(输入图的顶点数和弧数n);fflush(stdin);scanf(%d,%d,&G-vexnum,&G-arcnum);for(i=0;ivexnum;i+)printf(输入图的顶点n);fflush(stdin);scanf(%c,&G-vertexi.data);/*输入图的顶点*/G-vertexi.firstarc=NULL;getchar();for(j=1;jarcnum;j+)printf(请输入项临

4、街的两个节点)；scanf(%c,%c,&v1,&v2);getchar();k=LocateVertex(G,v1);m=LocateVertex(G,v2);s=(ArcNode*)malloc(sizeof(ArcNode);p=(ArcNode*)malloc(sizeof(ArcNode);p-nextarc=NULL;s-nextarc=NULL;p-adjvex=k;s-adjvex=m;p-nextarc=G-vertexm.firstarc;s-nextarc=G-vertexk.firstarc;G-vertexm.firstarc=p;G-vertexk.firstarc

5、=s;voidDaYin(AdjListg)inti;ArcNode*p;for(i=0;iadjvex);p=p-nextarc;voidDepthFirstSearch(AdjListg,intv0)/*图g为邻接表类型AdjList*/ArcNode*p;printf(%c,g.vertexv0.data);visitedv0=True;p=g.vertexv0.firstarc;while(p!=NULL)if(!visitedp-adjvex)DepthFirstSearch(g,p-adjvex);p=p-nextarc;/*DepthFirstSearch*/voidTraverseGraph(AdjListg)/*对图g进行深度优先搜索，Graph表示图的一种存储结构，如数组表示法或邻接表等*/intvi;for(vi=0;vig.vexnum;vi+)visitedvi=False;/*访问标志数组初始*/for(vi=0;vig.vexnum;vi+)/*调用深度遍历连通子图的操作*/if(!visitedvi)DepthFirstSearch(g,vi);/*若图g是连通图，则此循环