数据结构习题及答案

				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];
				}