[数据结构与算法]数据结构算法—邻接表存储有向图求两点间是否存在路径

数据结构算法—邻接表存储有向图求两点间是否存在路径

题目：试基于图的深度优先搜索策略编写一程序，判别以邻接表方式存储的有向图中是否存在有顶点Vi到Vj顶点的路径(i≠j)。

邻接表存储结构

typedef struct ArcNode{
	int adjvex;//边指向的顶点
	struct ArcNode *nextarc; // 下一条边的指针 
}ArcNode;
typedef struct VNode{
	int data;//顶点信息 
	ArcNode *fristarc;//该结点的第一条边 
}VNode,AdjList[MAX];
typedef struct {
	AdjList vertices;//头结点数组
	int vexnum,arcnum; // 图的当前顶点数和边数 
}ALGraph;
//寻找v1，v2在G中的位置
int LocateVex(ALGraph *G,int v){
	int i;
	for(i=0;i<=G->vexnum;i++)
		if(G->vertices[i].data==v)
			return i;
} 

求两点间是否存在路径算法思想：

依然是深度递归算法，从 Vi 出发 寻找与他邻接的边， 如果找到了 Vj 就说明存在路径，没有找到 就不存在路径 类似于 单一的弗洛伊德算法。

完整代码

#include<stdio.h>
#include<stdlib.h>
#define MAX 100
int vis[100];
int haspath = 0;
typedef struct ArcNode{
	int adjvex;//边指向的顶点
	struct ArcNode *nextarc; // 下一条边的指针 
}ArcNode;
typedef struct VNode{
	int data;//顶点信息 
	ArcNode *fristarc;//该结点的第一条边 
}VNode,AdjList[MAX];
typedef struct {
	AdjList vertices;//头结点数组
	int vexnum,arcnum; // 图的当前顶点数和边数 
}ALGraph;
//寻找v1，v2在G中的位置
int LocateVex(ALGraph *G,int v){
	int i;
	for(i=0;i<=G->vexnum;i++)
		if(G->vertices[i].data==v)
			return i;
} 
//创建图
void creatGraph(ALGraph *G){
	int i,j,k,m,n;
	ArcNode *s;
	printf("请输入图的顶点数和边数：");
	scanf("%d%d",&G->vexnum,&G->arcnum);
	getchar();//吃掉回车
	printf("请依次输入顶点集");
	for(i=0;i<G->vexnum;i++){
		scanf("%d",&G->vertices[i].data);
		getchar();
	}
	for(i=0;i<G->vexnum;i++)
		G->vertices[i].fristarc=NULL;
	for(k=0;k<G->arcnum;k++){
		printf("请输入一条边的起点和终点：");
		scanf("%d%d",&i,&j);
		m=LocateVex(G,i); // 找到输入结点的在 数组中的索引值。直接使用i，j 会出错。因为之后的插入和查找都是使用Adjlist数组 
		n=LocateVex(G,j);
		s=(ArcNode*)malloc(sizeof(ArcNode));//头插法  
		s->adjvex=j;
		s->nextarc=G->vertices[m].fristarc;
		G->vertices[m].fristarc=s;
	}
}
void readGraph(ALGraph G){//深度遍历图 
	int i,j;
	ArcNode *p;
	for(i=0;i<G.vexnum;i++){
		printf("%d V%d : ",i,G.vertices[i].data);
		for(p=G.vertices[i].fristarc;p;p=p->nextarc)
			printf(" ->V%d",p->adjvex);
		printf("\n");
	}
}
//求两点间是否存在路径
int existPath(int a,int b,ALGraph *G){
	int m,n;
	m=LocateVex(G,a);
	n=LocateVex(G,b);
	vis[m]=1;
	ArcNode *p;
	p = G->vertices[m].fristarc;
	//printf("p :%d\n",p->adjvex); 
	if(m == n) {
		haspath=1;
	}
	while(p){
		if(p->adjvex == b) { // 如果p的出边等于 b  意味着找到了 
			haspath= 1;
			break;
		}
		if(!vis[LocateVex(G,p->adjvex)]) // p的出边没有被访问 
			existPath(p->adjvex,b,G);   // 递归调用 
		p=p->nextarc;
	}
} 
void print_Path(int d,int z,ALGraph *G){//输出两点连接路径
	int m,n;
	m=LocateVex(G,d);
	n=LocateVex(G,z);
    ArcNode *p = G->vertices[m].fristarc;
    printf("\n路径为：V%d",d);
    while(p){
        printf("->V%d",p->adjvex);
        if(p->adjvex == z)break;
        p = G->vertices[LocateVex(G,p->adjvex)].fristarc;
    }printf("\n");
}
int main(){
	ALGraph G;
	creatGraph(&G);
	readGraph(G);
	int a,b;
	printf("判断a，b 之间是否存在路径：");
	scanf("%d%d",&a,&b);
	existPath(a,b,&G);
	if(haspath==1){
		printf("存在");
		print_Path(a,b,&G);
	}else{
		printf("不存在");
	}
}
运行结果实例：
1.
请输入图的顶点数和边数：6 3
请依次输入顶点集1 2 3 4 5 6
请输入一条边的起点和终点：1 2
请输入一条边的起点和终点：2 3
请输入一条边的起点和终点：3 4
0 V1 :  ->V2
1 V2 :  ->V3
2 V3 :  ->V4
3 V4 :
4 V5 :
5 V6 :
判断a，b 之间是否存在路径：1 4
存在
路径为：V1->V2->V3->V4
--------------------------------
Process exited after 11.74 seconds with return value 0
请按任意键继续. . .

2.
请输入图的顶点数和边数：6 3
请依次输入顶点集1 2 3 4 5 6
请输入一条边的起点和终点：1 2
请输入一条边的起点和终点：2 3
请输入一条边的起点和终点：3 4
0 V1 :  ->V2
1 V2 :  ->V3
2 V3 :  ->V4
3 V4 :
4 V5 :
5 V6 :
判断a，b 之间是否存在路径：4 6
不存在
--------------------------------
Process exited after 9.32 seconds with return value 0
请按任意键继续. . .