发布时间 : 星期六 文章数据结构作业系统 - 第七章答案更新完毕开始阅读
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];
1 / 14
typedef struct { AdjList vertices; } 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 k; ArcNode *p; visited[i]=1;
for(p=g.vertices[i].firstarc;p;p=p->nextarc){if(p){k=p->adjvex; if(k==j)return 1; if(visited[k]!=1)
if(DfsReachable(g,k,j))return 1;}} return 0;} 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'.*/
2 / 14
图的邻接表以及相关类型和辅助变量定义如下： 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; } ALGraph;
Status InitQue(Que &q); Status EnQue(Que &q, int e); Status DeQue(Que &q, int &e); Status QueEmpty(Que q); Status GetFront(Que q, int &e);
Status BfsReachable(ALGraph g, int i, int j)
/* Determine whether it exists path from vertex i to */
3 / 14
/* vertex j in digraph g with Breadth_First Search.*/ /* Array 'visited' has been initialed to 'false'.*/{Que q; int k,n; ArcNode *p; InitQue(q); EnQue(q,i);
while(!QueEmpty(q)){DeQue(q,k); visited[k]=1;
for(p=g.vertices[k].firstarc;p;p=p->nextarc){n=p->adjvex; if(n==j)return 1;
if(visited[n]!=1)EnQue(q,n);}} return 0;}
7.24③试利用栈的基本操作编写，按深度优先搜索策略 遍历一个强连通图的非递归形式的算法。算法中不规定具 体的存储结构，而将图Graph看成是一种抽象的数据类型。 实现下列函数：
void Traverse(Graph dig, VertexType v0, void(*visit)(VertexType)); /* Travel the digraph 'dig' with Depth_First Search. */ 图以及相关类型、函数和辅助变量定义如下： Status visited[MAX_VERTEX_NUM]; int LocateVex(Graph g, VertexType v);
4 / 14