數(shù)據(jù)結構作業(yè)系統(tǒng)-第七章答案

1、精品資料7.22 試基于圖的深度優(yōu)先搜索策略寫一算法，判別以鄰接表方式存儲的有向圖中是否存在由頂點 vi 到頂點 vj 的路徑 (i j) 。 注意：算法中涉及的圖的基本操作必須在此存儲結構上實現(xiàn)。實現(xiàn)下列函數(shù)：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題要求。試基于圖的廣度優(yōu)先搜索策略寫一算法。實現(xiàn)下列函數(shù)：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 試利用棧的基本操作編寫，按深度優(yōu)先搜索策略遍歷一個強連通圖的非遞歸形式的算法。算法中不規(guī)定具體的存儲結構，而將圖Graph看成是一種抽象的數(shù)據(jù)類型。實現(xiàn)下列函數(shù)：void Traverse(Graph dig, VertexType v0, void(*visit)(VertexType); /* Travel the digraph 'dig' with Depth_First Search. */圖以及相關類型、函數(shù)和輔助變量定義如下：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 的簡單路徑的算法。實現(xiàn)下列函數(shù)：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.*/圖的鄰接表以及相關類型、函數(shù)和輔助變量定義如下：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 的所有簡單路徑。實現(xiàn)下列函數(shù)：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*/圖的鄰接表以及相關類型、函數(shù)和輔助變量定義如下

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 試完成求有向圖的強連通分量的算法，并分析算法的時間復雜度。實現(xiàn)下列函數(shù)：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的路徑數(shù)。實現(xiàn)下列函數(shù)：int SimplePath(MGraph G, int i, int j, int k);/*求有向圖G 的頂點 i 到 j 之間長度為k 的簡單路徑條數(shù)*/圖的鄰接矩陣存儲結構的類型定義如下：typedef enum DG,DN,AG,AN GraphKind; /有向圖 ,有向網 , 無向圖 , 無向網頂點關系類型。對無權圖，用1( 是)或 0(否 )表示相鄰否；/ 對帶權圖，則為權值類型InfoType *info; /該弧相關信息的指針(可無 )ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef str