7.22.c

部分高校使用anyview编程测试数据结构习题,此代码为数据结构题集(c语言版)严蔚敏版的课后习题答案.专门提供给在anyview上运行,全部为通告代码

7.22③ 试基于图的深度优先搜索策略写一算法，
判别以邻接表方式存储的有向图中是否存在由顶
点vi到顶点vj的路径(i≠j)。 注意：算法中涉及
的图的基本操作必须在此存储结构上实现。
 
实现下列函数：
Status DfsReachable(ALGraph g, int i, int j);
/* Judge if it exists a path from vertex 'i' to    */
/* vertex 'j' in digraph 'g'.                      */
/* Array 'visited[]' has been initialed to 'false'.*/                       

图的邻接表以及相关类型和辅助变量定义如下：
Status visited[MAX_VERTEX_NUM];
typedef char VertexType;
typedef struct ArcNode {
    int adjvex;
    struct ArcNode *nextarc;
} ArcNode;

typedef struct VNode {
    VertexType data;
    ArcNode  *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;
Status DfsReachable(ALGraph g, int i, int j)
/* Judge if it exists a path from vertex 'i' to    */
/* vertex 'j' in digraph 'g'.                      */
/* Array 'visited[]' has been initialed to 'false'.*/                       
{ int v,k;
  ArcNode  *p;
  if(i==j) return ERROR;
  else                                     //DFS遍历i指向的结点
  {                                        //返回j点的访问标志，默认为false，访问过就为true
    visited[i]=TRUE;
    for(p=g.vertices[i].firstarc;p;p=p->nextarc)
     {
      k=p->adjvex;
      if(k==j) visited[j]=TRUE;            //打标记
       if(!visited[k])
         if(DfsReachable(g,k,j));          //递归访问
    }//for  
  }//else 
  return visited[j];
}