判断两个顶点之间是否有路径

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;iif(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\

printf(\"请输入%d个顶点的值(<%d个字符):\\n\ for(i=0;i<(*G).vexnum;++i) {

scanf(\"%s\ (*G).vertices[i].firstarc=NULL; }

printf(\"请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\\n\"); for(k=0;k<(*G).arcnum;++k) {

scanf(\"%s%s\ 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 DFS(ALGraph G,int m,char *w) {

int i,f=0; visited[m]=1;

for(i=FirstAdjVex(G,m);i>=0&&f==0;i=NextAdjVex(G,m,i)){ if(strcmp(G.vertices[i].data ,w)==0) {

printf(\"两顶点之间有路径\");return OK; }

if(!visited[i]) f=DFS(G,i,w); }

if(f==0)return 0; else return 1; }

void DFSTraverse(ALGraph G) {

int i,f,m;char v[5],w[5]; printf(\"请输入两个顶点:\\n\"); scanf(\"%s\ scanf(\"%s\

for(i=0;iif(strcmp(G.vertices[i].data,v)==0) m=i; }

f=DFS(G,m,w);

if(f==0)printf(\"两顶点之间没路径\"); }

void main()

{

ALGraph g;

CreateGraph(&g); DFSTraverse(g); }