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

1、精品资料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 t

2、o 'false'.*/图的邻接表以及相关类型和辅助变量定义如下：Status visitedMAX_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; ALG

3、raph;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;visitedi=1;for(p=g.verticesi.firstarc;p;p=p->nextarc)if(p)k=p-

4、>adjvex;if(k=j)return 1;if(visitedk!=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 'visi

5、ted' has been initialed to 'false'.*/图的邻接表以及相关类型和辅助变量定义如下：Status visitedMAX_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 ver

6、tices;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

7、to */* vertex j in digraph g with Breadth_First Search.*/* Array 'visited' has been initialed to 'false'.*/Queue q;可编辑修改精品资料int k,n;ArcNode *p;InitQueue(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)retu

8、rn 1;if(visitedn!=1)EnQueue(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 visitedMAX_VERTE

9、X_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 InitStack(SStack &s);Status Push(SStack &s, SElemType x);Status Pop(SStack &s, SElemType &x);Status StackEmpty(

10、SStack s);Status GetTop(SStack s, SElemType &e);void Traverse(Graph dig,VertexType v0, void (*visit)(VertexType)inti,v,flag;SStack s;VertexTypep;/flag来记录某点还有没有邻接点可编辑修改精品资料InitStack(s);if(dig.vexnum&&dig.arcnum) i=LocateVex(dig,v0);visitedi=TRUE;visit(v0);Push(s,v0);while(!StackEmpty(s)Ge

11、tTop(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 采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k 的简单路径的算法。实现下列函数：Status SinglePath(ALGraph g, VertexType sv, V

12、ertexType 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 ifexists.*/图的邻接表以及相关类型、函数和辅助变量定义如下：Status visitedMAX_VERTEX_NUM;typedef charStrARR100MAX_VERTEX_NUM+1;typedef char VertexType;typedef struct ArcNode int adjvex;stru

13、ct 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, VertexType v);void inpath(char *&path, VertexType v);/* Add vertex 'v' to 'path

14、' */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 ifexists.*/int i,

15、j,l;ArcNode *p;if(sv=tv && k=0) inpath(sp,tv);return OK; elsei=LocateVex(g,sv);visitedi=1;inpath(sp,sv);for(p=g.verticesi.firstarc;p;p=p->nextarc)l=p->adjvex;if(!visitedl)if(SinglePath(g,g.verticesl.data,tv,k-1,sp)return OK;elsedepath(sp,g.verticesl.data);visitedi=0;7.28 已知有向图和图中两个顶点 u

16、 和 v，试编写算法求有向图中从 u 到 v 的所有简单路径。实现下列函数：void AllPath(ALGraph g, VertexType sv, VertexType tv,StrARR &path, int &i);/* Get all the paths from vertex sv to tv, save them */* into Array path which contains string components. */可编辑修改精品资料/* Return the number of path using i*/图的邻接表以及相关类型、函数和辅助变量定义如下

17、：Status visitedMAX_VERTEX_NUM;typedef 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; ALGr

18、aph;int LocateVex(Graph g, VertexType v);void inpath(char *path, VertexType v);/* Add vertex 'v' to 'path' */void depath(char *path, VertexType v);/* Remove vertex 'v' from 'path' */void AllPath2(ALGraph g, VertexType sv, VertexType tv,StrARR &path, int &i,int

19、 &d,VertexType A) int j,k,l,m,n;ArcNode *p;j=LocateVex(g,sv);visitedj=1;Ad+=sv;if(sv=tv)m=0;for(n=0;n<d;n+)pathim+=An;i+;elsefor(p=g.verticesj.firstarc;p;p=p->nextarc)可编辑修改精品资料l=p->adjvex;if(!visitedl)AllPath2(g,g.verticesl.data,tv,path,i,d,A);visitedj=0;d-;void AllPath(ALGraph g, Verte

20、xType sv, VertexType tv,StrARR &path, int &i)/* Get all the paths from vertex sv to tv, save them */* into Array path which contains string components. */* Return the number of path using i*/int d=0,j,l;VertexType AMAX_VERTEX_NUM,BMAX_VERTEX_NUM;for(l=0;l<5;l+)strcpy(B,pathl);for(j=0;j<

21、;strlen(pathl);j+)depath(pathl,Bj);AllPath2(g,sv,tv,path,i,d,A);7.31 试完成求有向图的强连通分量的算法，并分析算法的时间复杂度。实现下列函数：void StronglyConnected(OLGraph dig, StrARR &scc, int &n);/* Get all the strongly connected components in the digraph dig, */* and put the ith into scci which is a string.*/图的十字链表以及相关类型和辅助

22、变量定义如下：Status visitedMAX_VERTEX_NUM;int finishedMAX_VERTEX_NUM;typedef char StrARRMAX_VERTEX_NUMMAX_VERTEX_NUM+1; /记录各强连通分量typedef struct ArcBox int tailvex,headvex;struct ArcBox *hlink,*tlink; ArcBox;typedef struct VexNode VertexType data;可编辑修改精品资料ArcBox*firstin,*firstout; VexNode; typedef struct V

23、exNode xlistMAX_VERTEX_NUM;intvexnum, arcnum; OLGraph;int count;void DFS1(OLGraph dig,int v);void DFS2(OLGraph dig,int v,StrARR &scc,int j,int k);void StronglyConnected(OLGraph dig, StrARR &scc, int &n)/* Get all the strongly connected components in the digraph dig, */* and put the ith i

24、nto scci which is a string.*/int i,k=0,v;count=0;for(v=0;v<dig.vexnum;v+)if(!visitedv)DFS1(dig,v);for(v=0;v<dig.vexnum;v+)visitedv=0;for(i=dig.vexnum-1;i>=0;i-)v=finishedi;if(!visitedv)DFS2(dig,v,scc,n,k);n+;void DFS1(OLGraph dig,int v)int w;ArcBox *p;visitedv=1;for(p=dig.xlistv.firstout;p;

25、p=p->tlink) w=p->headvex;if(!visitedw)DFS1(dig,w);可编辑修改typedef struct VRType adj; /精品资料finishedcount+=v;void DFS2(OLGraph dig,int v,StrARR &scc,int j,int k)int w;ArcBox *p;visitedv=1;sccjk+=dig.xlistv.data;for(p=dig.xlistv.firstin;p;p=p->hlink)w=p->tailvex;if(!visitedw)DFS2(dig,w,scc

26、,j,k);7.29 试写一个算法，在以邻接矩阵方式存储的有向图 G 中求顶点i 到顶点 j 的不含回路的、长度为k的路径数。实现下列函数：int SimplePath(MGraph G, int i, int j, int k);/*求有向图G 的顶点 i 到 j 之间长度为k 的简单路径条数*/图的邻接矩阵存储结构的类型定义如下：typedef enum DG,DN,AG,AN GraphKind; /有向图 ,有向网 , 无向图 , 无向网顶点关系类型。对无权图，用1( 是)或 0(否 )表示相邻否；/ 对带权图，则为权值类型InfoType *info; /该弧相关信息的指针(可无 )ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef str