數(shù)據(jù)結(jié)構(gòu)作業(yè)系統(tǒng)答案

1、7.22 試基于圖的深度優(yōu)先搜索策略寫一算法，判別以鄰接表方式存儲(chǔ)的有向圖中是否存在由頂點(diǎn)vi到頂點(diǎn)vj的路徑(ij)。 注意：算法中涉及的圖的基本操作必須在此存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)。 實(shí)現(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 to 'f

2、alse'.*/ 圖的鄰接表以及相關(guān)類型和輔助變量定義如下：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; ALGrap

3、h;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)

4、 k=p->adjvex; if(k=j)return 1; if(visitedk!=1) if(DfsReachable(g,k,j)return 1; return 0;7.23 同7.22題要求。試基于圖的廣度優(yōu)先搜索策略寫一算法。實(shí)現(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 'vis

5、ited' has been initialed to 'false'. */圖的鄰接表以及相關(guān)類型和輔助變量定義如下：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 AdjLis

6、t vertices; 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 ve

7、rtex 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); EnQueue(q,i); while(!QueueEmpty(q) DeQueue(q,k); visitedk=1; for(p=g.verticesk.firstarc;p;p=p->nextarc) n=p->adjvex;

8、if(n=j)return 1; if(visitedn!=1)EnQueue(q,n); return 0;7.24 試?yán)脳５幕静僮骶帉?，按深度?yōu)先搜索策略遍歷一個(gè)強(qiáng)連通圖的非遞歸形式的算法。算法中不規(guī)定具體的存儲(chǔ)結(jié)構(gòu)，而將圖Graph看成是一種抽象的數(shù)據(jù)類型。實(shí)現(xiàn)下列函數(shù)：void Traverse(Graph dig, VertexType v0, void(*visit)(VertexType);/* Travel the digraph 'dig' with Depth_First Search. */圖以及相關(guān)類型、函數(shù)和輔助變量定義如下：Status visi

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

10、 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來記錄某點(diǎn)還有沒有鄰接點(diǎn) InitStack(s); if(dig.vexnum&&dig.arcnum) i=LocateVex(dig,v0);visitedi=TRUE;visit(v0);Push(s,v0); while(!Stac

11、kEmpty(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 采用鄰接表存儲(chǔ)結(jié)構(gòu)，編寫一個(gè)判別無向圖中任意給定的兩個(gè)頂點(diǎn)之間是否存在一條長(zhǎng)度為k的簡(jiǎn)單路徑的算法。實(shí)現(xiàn)下列函數(shù)：Status SinglePath(ALGraph g, V

12、ertexType 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. */圖的鄰接表以及相關(guān)類型、函數(shù)和輔助變量定義如下：Status visitedMAX_VERTEX_NUM;typedef char StrARR100MAX_VERTEX_NUM+1;typedef char VertexType;typedef struct ArcN

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

14、9; 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 i

15、f exists. */ int i,j,l; ArcNode *p; if(sv=tv && k=0) inpath(sp,tv); return OK; else i=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; else depath(sp,g.verticesl.data

16、); visitedi=0; 7.28 已知有向圖和圖中兩個(gè)頂點(diǎn)u和v，試編寫算法求有向圖中從u到v的所有簡(jiǎn)單路徑。實(shí)現(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 */圖的鄰接

17、表以及相關(guān)類型、函數(shù)和輔助變量定義如下：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; i

18、nt vexnum, arcnum; ALGraph;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

19、 &path, int &i,int &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+; else for(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;

20、 d-; 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 */ int d=0,j,l; VertexType AMAX_VERTEX_NUM,BMAX_VERTEX_NUM; for(l=0

21、;l<5;l+) strcpy(B,pathl); for(j=0;j<strlen(pathl);j+) depath(pathl,Bj); AllPath2(g,sv,tv,path,i,d,A); 7.31 試完成求有向圖的強(qiáng)連通分量的算法，并分析算法的時(shí)間復(fù)雜度。實(shí)現(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 i

22、nto scci which is a string. */圖的十字鏈表以及相關(guān)類型和輔助變量定義如下：Status visitedMAX_VERTEX_NUM;int finishedMAX_VERTEX_NUM;typedef char StrARRMAX_VERTEX_NUMMAX_VERTEX_NUM+1; / 記錄各強(qiáng)連通分量typedef struct ArcBox int tailvex,headvex; struct ArcBox *hlink,*tlink; ArcBox;typedef struct VexNode VertexType data; ArcBox *firs

23、tin,*firstout; VexNode;typedef struct VexNode xlistMAX_VERTEX_NUM; int vexnum, 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

24、in the digraph dig, */* and put the ith into 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)

25、 int w; ArcBox *p; visitedv=1; for(p=dig.xlistv.firstout;p;p=p->tlink) w=p->headvex; if(!visitedw) DFS1(dig,w); 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->tai

26、lvex; if(!visitedw) DFS2(dig,w,scc,j,k); 7.29 試寫一個(gè)算法，在以鄰接矩陣方式存儲(chǔ)的有向圖G中求頂點(diǎn)i到頂點(diǎn)j的不含回路的、長(zhǎng)度為k的路徑數(shù)。 實(shí)現(xiàn)下列函數(shù)：int SimplePath(MGraph G, int i, int j, int k);/* 求有向圖G的頂點(diǎn)i到j(luò)之間長(zhǎng)度為k的簡(jiǎn)單路徑條數(shù) */圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)的類型定義如下：typedef enum DG,DN,AG,AN GraphKind; / 有向圖,有向網(wǎng),無向圖,無向網(wǎng)typedef struct VRType adj; / 頂點(diǎn)關(guān)系類型。對(duì)無權(quán)圖，用1(是)或0(否)表示相鄰否； / 對(duì)帶權(quán)圖，則為權(quán)值類型 InfoType *info; / 該弧相關(guān)信息的指針(可無)ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef stru