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

1、最新资料推7.22试基于图的深度优先搜索策路写一算法， 判别以邻接表方式存储的有向图中是否存在由顶 点vi到顶点vj的路径(iHj)。注意：算法中涉及 的图的基本操作必须在此存储结构上实现。实现下列函数：Status DfsReachable(ALGraph g. int i, int j);/* Judge if it exists a path from vertex i to */* vertex 了 in digraph g.*/* Array visitedJ has been initialed to false.*/图的邻接表以及相关类型和辅助变量定义如下：Status visi

2、ted(MAX_VERTEX_NUM ;typedef char VertexType;typedef stnict ArcNode int adjvex;struct ArcNode *nextarc; ArcNode;typedef stnict VNode VertexType data;ArcNode *firstarc; VNode, AdjListMAX_VERTEX_NUM;typedef stnict Adj List vertices;int vexnum arcnum; ALGraph:Status DfsReachable(ALGraph g, int i, int j)

3、/* Judge if it exists a path from vertex 丫 to */* vertex 了 in digraph g*/* Array isitedf1 has been initialed to Talsc.*/int k;ArcNode *p;visitedi=I;for(p=g.verticesi.firstarc;p;p=p-nextarc)if(p)(k=p-adjvex;if(k=j)return 1;if(visitedk|!=l)if(DfsRcachable(g,kj)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 visited(MAX_VERTEX_NUMJ;typcdef char VertexType;typcdef

5、stnict ArcNode int adjvex;struct ArcNode *nextarc;)ArcNode;typcdef stnict VNode VertexType data;ArcNode *firstarc;)VNode, AdjListIMAX_VERTEX_NUM|;typcdef stnict Adj List vertices;int vexnum arcnum; ALGraph:Status InitQueue(Queue &q);Status EnQueue(Queue &q. int e);Status DeQucue(Queue &q. int &c);St

6、atus QucueEmpty(Queue q);Status GetFront(Queue q, int &c);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;InitQueue(q);EnQu

7、eue(q.i);while( !QueueEmpty(q)DcQueue(q,k);visitedk=l;for(p=g.verticesk.firstarc;p;p=p-nextarc)(n=p-adjvex;if(n=j)return 1:if(visited(n!=l)EnQueue(qji);return 0;)7.24试利用栈的基本操作编写，按深度优先搜索策略 遍历一个强连通图的非递归形式的算法。算法中不规左具 体的存储结构，而将图Graph看成是一种抽象的数据类型。实现下列函数：void Traverse(Graph dig. VertexType vO. void(*visit

8、)(VertexTjpe);/* Travel the digraph dig with Depth_First Search. */图以及相关类型、函数和辅助变量左义如下：Status visitedMAX_VERTEX_NUMl;int LocateVcx(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

9、 &s);Status Push(SStack &s. SElemType x);Status Pop(SStack &s, SElemType &x);Status StackEmpty(SStack s);Status GetTop(SStack s, SElemType &c);void Traverse(Graph dig, VertexType vO, void (*visit)(VertexTpe)int i,v,flag;SStack s;VertexTypc p; InitStack(s);/flag来记录某点还有没有邻接点if(dig.vexnuni&dig.arcnum)

10、i=LocateVex(dig.vO);visitedi=TRUE;visit(vO);Push(SArO);while(! StackEmpty(s)GetTop(s,p);v=LocateVex(dig.p);flag=0;for(i=FirstAdjVex(dig,v);i=0;i=NextAdjVex(digAr,i) if(!visitedi) p=GetVex(digJ); flag=l; break;if(flag)visit(p);visitedi=TRUE;Push(s.p);elsePop(s,p); 7.27采用邻接表存储结构，编写一个判别无向图中任意给左的 两个顶点之间

11、是否存在一条长度为k的简单路径的算法。实现下列函数：Status SinglePath(ALGraph g, VertexType sv, VcricxTypc 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_NUMl;typcdcf char StrARR 100MAX_V

12、ERTEX_NUM+1;typcdcf char VertexType;typcdcf stnict ArcNode int adjvex;struct ArcNode *nextarc;)ArcNode;typedef stnict VNode VertexType data;ArcNode *firstarc; VNode, AdjListMAX_VERTEX_NUM;typedef stnict AdjList vertices;int vexnum arcnum; ALGraph:int LocateVex(Graph g, VertexType v);void inpath(char

13、 *&path、VertexType v);/* Add vertex V to path */void depath(char *&palh. 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

14、 exists.*/ intArcNode *p;if(sv=tv & k=0) inpath(sp,tv);return OK: elsei=LocateVex(g,sv);visitedi=l;inpath(sp.sv);for(p=g.verticesi.firstarc;p;p=p-nextarc)(l=p-adjvex;if(!visitedl)if(SinglePath(g,g.verticesl.dataJv,k-l,sp)return OK:elsedepath(sp.g.verticesl.data);)visitedi=O;7.28 已知有向图和图中两个顶点u和v,试编写算

15、法求 有向图中从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*/图的邻接表以及相关类型、函数和辅助变量是义如下： Status visited(MAX_VERTEX_NUMJ;

16、typedef char StrARR100MAX_VERTEX_NUM+1 ; typcdef char VertexTvpe;typedef stmet ArcNode int adjvex;struct ArcNode *nextarc;)ArcNode;typedef stmet VNode VertexType data;ArcNode *firstarc; VNode, AdjListMAX_VERTEX_NUM;typedef stnict Adj List vertices;int vexnuni arcnum; ALGraph;int LocateVex(Graph g, V

17、ertexType v);void inpath(char *patlr VertexType v);/* Add vertex V to path */void depath(char *path, VertexType v);/* Remove vertex V from path */void AllPath2(ALGraph g, VertexTSpe sv, VertexType tv, StrARR &path, int &i,int &d,VertexType A) int j,k丄m.n;ArcNode *p;j=LocateVex(g,sv);visitedj=l;Ad+=s

18、v;if(sv=tv)m=0;for(n=0;nnextarc)l=p-adjvex;if(!visitedl)AllPath2(g,g.verticesl.data,tv;pathJ.d,A);visitedj=O;d_；void AllPath(ALGraph g, VertexTpe sv. VertexType tv,StrARR &palh. int &i)/* Get all the paths from vertex sv to tv, save them */* into Array path which contains string components */* Retur

19、n the number of path using i*/int d=O,jJ;VertexType AMAX_VERTEX_NUM.B|MAX_VERTEX_NUM;for(l=0;l5;l+)strcpy(B.pathl);for(j=0;jstrlen(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 s

20、trongly connected components in the digraph dig, */* and put the ith into scci which is a string*/图的十字链表以及相关类型和辅助变量立义如下：Status visited(MAX.VERTEX.NUM ;int finishedMAX_VERTEX_NUM;typcdcf char StrARRMAX_VERTEX_NUMMAX_VERTEX_NUM+l; / 记录齐强连通分疑 typcdcf stmct ArcBox int tailvex,headvex;struct ArcBox *hlin

21、k?tlink; ArcBox;typcdcf stnict VexNode VertexType data;ArcBox *firstiiL*firstout; VexNode;typcdcf stnict VexNode xlist(MAX_VERTEX_NUM;int vexnuni, arcnum; OLGraph;int count;void DFSl(OLGraph digjnt v);void DFS2(OLGraph digjnt v.StrARR &sccjnt jjnt k);void StrongIyConnected(OLGraph dig, StrARR &scc,

22、int &n)/* Get all the strongly connected components in the digraph dig, */* and put the ith into scci which is a string*/int i,k=0,v;count=0;for(v=0;vdig.vexnum;v+)if(!visitedv)DFSl(dig.v);for(v=0;v=0:i-)v=finishedi;if(!visitedv)DFS2(dig,v,scc,n,k);n+;)void DFSKOLGraph digjnt v)int w;ArcBox *p;visit

23、edv=l;for(p=dig.xlistv.firstout;p;p=p-tlink) w=p-headvex;if(!visitedw)DFSl(dig,w);finishcdcount+=v;void DFS2(OLGraph digjnt v.StrARR &secant j,int k)int w;ArcBox *p;visitedv=l;sccjk+=dig.xlistv.data;for(p=dig.xlistv.firstin;p;p=p-hlink)w=p-tailvex;if(!visitedw)DFS2(dig,w,scc、j,k);7.29试写一个算法，在以邻接矩阵方式

24、存储的有向图G中求顶点i到顶点j的不含回路的、长度为k 的路径数。实现下列函数：int SimplePath(MGraphG inti, int j, int k);/*求有向图G的顶点i到j之间长度为k的简单路径条数*/图的邻接矩阵存储结构的类型定义如下：typcdef enum DGDN.AGAN GraphKind: / 有向图，有向网，无向图,无向网typcdcf stnict VRTypcadj;/顶点关系类型。对无权图，用1(是)或0(否)表示相邻否: /对带权图，则为权值类型InfoType *info; /该弧相关信息的指针(可无) ArcCell.AdjMatrix(MAX_VERTEX_NUMnMAX_VERTEX_NUM;typcdcf stnic