数据结构作业系统 - 第七章答案

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