1、在主函数中输出每个顶点的数据域及其所有邻接点;从键盘读入两个顶点vs、vt()的数据域,调用函数Path()判断其间是否存在路径;(2) CreateAdjList():建立有向图邻接表。功能:从键盘接收各顶点数据域及各条有向边所依附的顶点(如:“2,3”代表该边依附的两个顶点在表头数组中的下标为2和3),要求单链表中结点按数据域升序排序;(3) Path(): 判断两顶点间是否存在路径,如果存在,将打印该路径(若存在多条路径,打印其中一条即可)。例:输入:请输入顶点和边的数目:8,9 /(在main()函数中输入) 请输入各顶点数据域:a b c d e f g h/(在CreateAdjL
2、ist()中输入) 请输入各条边:1,2 1,3 2,4 3,6 3,7 4,8 5,2 5,8 6,7 输出:图的邻接表为:a 2 3 /(在main()函数中输出) b 4 c 6 7 d 8 e 2 8 f 7 g h 输入: 请输入要查找是否存在路径的顶点:a,h 顶点a和d之间存在路径,路经为:a b d ha,e 顶点a和e之间不存在路径参考答案:#includemalloc.h#define Max_Vertex_Num 10typedef char VertexType;int visitedMax_Vertex_Num;int visitpathMax_Vertex_Num;
3、int pathvexnum;int flag;/单链表结点(弧结点)typedef struct Arcnode int adjvex; /该弧所指向顶点(在表头数组中)的位置 struct Arcnode *nextarc; /指向依附该顶点下一条边或弧 ArcNode;/头结点typedef struct Vnode VertexType data; /顶点信息 Arcnode *firstarc; /指向第一条依附该顶点的弧 VNode, AdjListMax_Vertex_Num;/图的定义typedef struct AdjList vertices; / 表头数组 int vex
4、num, arcnum; / 图中顶点及弧的数目 ALGraph;/建立邻接表void CreateAdjList (ALGraph &G) int k,i,j; ArcNode *p,*q,*s; for(k=1;kadjvex=j;nextarc=NULL; q=NULL; p=G.verticesi.firstarc; while(p!=NULL)&(jp-adjvex) q=p; p=p-nextarc; if(p=NULL&q=NULL) G.verticesi.firstarc=s; else if(p=NULL&q!=NULL) q-nextarc=s; else if(p!=N
5、ULL& s-nextarc=p; else/按深度优先判断顶点vx和vy间是否存在路径void DFSPath(ALGraph G, int v, VertexType vy) ArcNode *w; int i; visitpath+pathvexnum=v; visitedv=1; w=G.verticesv.firstarc; /顶点v的第一个邻接点 while(w!=NULL) /是否存在 i=w-adjvex; /邻接点下标 if(G.verticesi.data=vy) flag=1; return; else if(flag=0&visitedi=0) DFSPath(G,i,vy); w=w- /v的下一个邻接点 if(flag=0) pathvexnum-;/从路径上删除Vvoid Path(ALGraph G, VertexType vx, VertexType vy) for(i=1;iadjvex); p=p-请输入需判断是否存在路径的两个顶点: fflush(stdin);%c,%cvx,&vy); Path(G,vx,vy);
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2