《数据结构作业系统第七章答案》由会员分享，可在线阅读，更多相关《数据结构作业系统第七章答案（10页珍藏版）》请在金锄头文库上搜索。
1、7.22 试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(ij)。 注意：算法中涉及的图的基本操作必须在此存储结构上实现。 实现下列函数：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 visitedMA
2、X_VERTEX_NUM;typedef char VertexType;typedef struct ArcNode int adjvex; struct ArcNode *nextarc; ArcNode;typedef struct VNode VertexType data; ArcNode *firstarc; VNode, AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum, arcnum; ALGraph;Status DfsReachable(ALGraph g, int i, int j)/* J
3、udge 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; visitedi=1; for(p=g.verticesi.firstarc;p;p=p-nextarc) if(p) k=p-adjvex; if(k=j)return 1; if(visitedk!=1) if(DfsReachable(g,k,j)return 1; return 0;7.23 同7.22题要求。试基于
4、图的广度优先搜索策略写一算法。实现下列函数：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 visitedMAX_VERTEX_NUM;typedef char VertexType;typ
5、edef struct ArcNode int adjvex; struct ArcNode *nextarc; ArcNode;typedef struct VNode VertexType data; ArcNode *firstarc; VNode, AdjListMAX_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
6、&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. */ Queue q; int k,n; ArcNode *p; InitQ
7、ueue(q); EnQueue(q,i); while(!QueueEmpty(q) DeQueue(q,k); visitedk=1; for(p=g.verticesk.firstarc;p;p=p-nextarc) n=p-adjvex; if(n=j)return 1; if(visitedn!=1)EnQueue(q,n); return 0;7.24 试利用栈的基本操作编写，按深度优先搜索策略遍历一个强连通图的非递归形式的算法。算法中不规定具体的存储结构，而将图Graph看成是一种抽象的数据类型。实现下列函数：void Traverse(Graph dig, VertexType
8、 v0, void(*visit)(VertexType);/* Travel the digraph dig with Depth_First Search. */图以及相关类型、函数和辅助变量定义如下：Status visitedMAX_VERTEX_NUM;int LocateVex(Graph g, VertexType v);VertexType GetVex(Graph g, int i);int FirstAdjVex(Graph g, int v);int NextAdjVex(Graph g, int v, int w);void visit(char v);Status I
9、nitStack(SStack &s);Status Push(SStack &s, SElemType x);Status Pop(SStack &s, SElemType &x);Status StackEmpty(SStack s);Status GetTop(SStack s, SElemType &e);void Traverse(Graph dig, VertexType v0, void (*visit)(VertexType) int i,v,flag;SStack s;VertexType p; /flag来记录某点还有没有邻接点 InitStack(s); if(dig.v
10、exnum&dig.arcnum) i=LocateVex(dig,v0);visitedi=TRUE;visit(v0);Push(s,v0); while(!StackEmpty(s) GetTop(s,p);v=LocateVex(dig,p);flag=0; for(i=FirstAdjVex(dig,v);i=0;i=NextAdjVex(dig,v,i) if(!visitedi) p=GetVex(dig,i); flag=1; break; if(flag) visit(p);visitedi=TRUE; Push(s,p); elsePop(s,p); 7.27 采用邻接表存
11、储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。实现下列函数：Status SinglePath(ALGraph g, VertexType sv, VertexType tv, int k, char *sp);/* Judge whether it exists a path from sv to tv with length k */* in graph g, return path using string sp if exists. */图的邻接表以及相关类型、函数和辅助变量定义如下：Status visitedMAX_VERTEX_NUM;t
12、ypedef char StrARR100MAX_VERTEX_NUM+1;typedef char VertexType;typedef struct ArcNode int adjvex; struct ArcNode *nextarc; ArcNode;typedef struct VNode VertexType data; ArcNode *firstarc; VNode, AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum, arcnum; ALGraph;int LocateVex(Graph g,
13、VertexType v);void inpath(char *&path, VertexType v); /* Add vertex v to path */void depath(char *&path, VertexType v); /* Remove vertex v from path */Status SinglePath(ALGraph g, VertexType sv, VertexType tv, int k, char *sp)/* Judge whether it exists a path from sv to tv with length k */* in graph g, return path using string sp if exists. */ int i,j,l; ArcNode *p; if(
