判断有向图中两点之间是否存在路径

《判断有向图中两点之间是否存在路径》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、#include#include#include#defineDL30#defineMax50intflag=0;intvisited[Max];typedefstructEdge//边、桥{intVnum;//边上挂着要指向的点的编号structEdge*next;//边和点的指针类型相同}Edge;typedefstructVert//点{intVNO;//点序号charVname[DL];//点名称Edge*head;//边和点的指针类型相同}Vert;typedefstruct{Ver

2、tList[Max];//地图上最多有Max个点intnum_vert;//点的个数intnum_edge;//边的个数}Map;voidCreateMap(Map*HF);voidPrint(Map*HF);voidDFS(Map*HF,inti,intj);voidCheck(Map*HF);voidClearMap(Map*HF);voidmain(){Map*HF;HF=(Map*)malloc(sizeof(Map));CreateMap(HF);Print(HF);Check(HF);ClearMap(HF);}voidCreateMa

3、p(Map*HF){inti,j;Edge*E;printf("输入图中，点的个数：");scanf("%d",&HF->num_vert);for(i=0;inum_vert;i++){printf("输入点.%d的名称：",i);scanf("%s",HF->List[i].Vname);HF->List[i].head=NULL;}printf("输入图中，边的个数：");scanf("%d",&HF->num_edge);for(i=0;inum_edge;i++){E=(Edge*)malloc(sizeof(Edge

4、));printf("t第%d条边：起点序号：",i+1);scanf("%d",&j);//起点printf("终点序号：");scanf("%d",&E->Vnum);//终点E->next=HF->List[j].head;HF->List[j].head=E;}}voidPrint(Map*HF){Edge*E=NULL;inti;for(i=0;inum_vert;i++){E=HF->List[i].head;if(E==NULL)printf("路径从%s出发分别到达：",HF->List[i].Vname);el

5、se{printf("路径从%s出发分别到达：",HF->List[i].Vname);while(E!=NULL){printf("%s",HF->List[E->Vnum].Vname);E=E->next;}}}}voidDFS(Map*HF,inti,intj){Edge*p;visited[i]=1;p=HF->List[i].head;while(p!=NULL){if(visited[p->Vnum]==0){if(p->Vnum==j)flag=1;if(flag==1)return;DFS(HF,p->Vnum,j);}p=p

6、->next;}return;}voidCheck(Map*HF){inti,j;for(i=0;i<=HF->num_vert;i++)visited[i]=0;printf("测试【任意两点间是否存在路径】");printf("输入起点序号");scanf("%d",&i);printf("输入终点序号");scanf("%d",&j);DFS(HF,i,j);if(flag==1)printf("%s→%s成功",HF->List[i].Vname,HF->List[j].Vname);if(flag==0)printf("%s→

7、%s失败",HF->List[i].Vname,HF->List[j].Vname);}voidClearMap(Map*HF){inti;Edge*p,*q;for(i=0;inum_vert;i++){p=HF->List[i].head;while(p!=NULL){q=p->next;free(p);p=q;}}}