7.23.c

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

7.23③ 同7.22题要求。试基于图的广度优先搜索策略写一算法。

实现下列函数：
Status BfsReachable(ALGraph g, int i, int j); 
/* Determine whether it exists path from vertex i to */
/* vertex j in digraph g with Breadth_First Search.  */
/* 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 InitQueue(Queue &q);
Status EnQueue(Queue &q, int e);
Status DeQueue(Queue &q, int &e);
Status QueueEmpty(Queue q);
Status GetFront(Queue q, int &e);
Status BfsReachable(ALGraph g, int i, int j) 
/* Determine whether it exists path from vertex i to */
/* vertex j in digraph g with Breadth_First Search.  */
/* Array 'visited' has been initialed to 'false'.    */
{ 
  int v,k;
  Queue Q;
  ArcNode  *p; 
  if(i==j) return ERROR;
  InitQueue(Q);
  EnQueue(Q,i);
  while(!QueueEmpty(Q))                    //BFS遍历i指向的结点
  {                                        //返回j点的访问标志，默认为false，访问过就为true
    DeQueue(Q,v);
    visited[v]=TRUE;
    for(p=g.vertices[v].firstarc;p;p=p->nextarc)
     {
      k=p->adjvex;
      if(k==j) visited[j]=TRUE;            //打标记
      if(!visited[k]) EnQueue(Q,k);        //入队列
    }//for  
  }//while
  return visited[j];
}