Question

数据结构 判断两顶点间是否有路径

Answer 1

判断图中两个顶点之间是否有路径的算法实现（按深度优先遍历方式）
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status;
#define MAX_NAME 5 /* 顶点字符串的最大长度*/
typedef int VRType;
typedef char VertexType[MAX_NAME];
#define MAX_VERTEX_NUM 20 /* 最大顶点个数 */
typedef struct ArcNode
{
int adjvex; /* 该弧所指向的顶点的位置 */
struct ArcNode *nextarc; /* 指向下一条弧的指针 */
}ArcNode; /* 表结点 */
typedef struct
{
VertexType data; /* 顶点信息 */
ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧(或边)的指针 */
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum,arcnum; /* 图的当前顶点数和弧数 */
}ALGraph;
int LocateVex(ALGraph G,VertexType u)
{ /* 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vertices[i].data)==0)
return i;
return -1;
}
int FirstAdjVex(ALGraph G,int v)
{ /* 返回第v个顶点的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */
ArcNode *p;
p=G.vertices[v].firstarc;
if(p)
return p->adjvex;
else
return -1;
}
int NextAdjVex(ALGraph G,int v,int w)
{
ArcNode *p;
p=G.vertices[v].firstarc;
while(p&&p->adjvex!=w)
p=p->nextarc;
if(!p||!p->nextarc)
return -1;
else
return p->nextarc->adjvex;
}
Status CreateGraph(ALGraph *G)
{
int i,j,k;
VertexType va,vb;
ArcNode *p;
printf("请输入图的顶点数,边数: ");
scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);
printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i)
{
scanf("%s",(*G).vertices[i].data);
(*G).vertices[i].firstarc=NULL;
}
printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n");
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s",va,vb);
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
p->nextarc=(*G).vertices[i].firstarc; /* 插在表头 */
(*G).vertices[i].firstarc=p;
/* 因为无向图,产生第二个表结点 */
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=i;
p->nextarc=(*G).vertices[j].firstarc; /* 插在表头 */
(*G).vertices[j].firstarc=p;
}
return OK;
}
int visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */
int found=0;
void DFS(ALGraph G,int v,int vv)
{
int w;
visited[v]=TRUE;
for(w=FirstAdjVex(G,v);w>=0&&found==0;w=NextAdjVex(G,v,w))
if(w==vv) found=1;
else if(!visited[w]) DFS(G,w,vv);

}
void DFSTraverse(ALGraph G)
{
int v,v1,v2;
VertexType va,vb;
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE;
printf("请输入要判断的路径 ");
scanf("%s%s",va,vb);
v1=LocateVex(G,va);
v2=LocateVex(G,vb);
DFS(G,v1,v2);

}
void main()
{
ALGraph g;
CreateGraph(&g);
DFSTraverse(g);
if(found==1) printf("\n有路径！");
else printf("无路径！");
}