數據結構作業(yè)系統(tǒng)答案

1、7.22 試基于圖的深度優(yōu)先搜索策略寫一算法，判別以鄰接表方式存儲的有向圖中是否存在由頂點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 'f

2、alse'.*/ 圖的鄰接表以及相關類型和輔助變量定義如下：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)先搜索策略寫一算法。實現下列函數：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'. */圖的鄰接表以及相關類型和輔助變量定義如下：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ōu)先搜索策略遍歷一個強連通圖的非遞歸形式的算法。算法中不規(guī)定具體的存儲結構，而將圖Graph看成是一種抽象的數據類型。實現下列函數：void Traverse(Graph dig, VertexType v0, void(*visit)(VertexType);/* Travel the digraph 'dig' with Depth_First Search. */圖以及相關類型、函數和輔助變量定義如下：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來記錄某點還有沒有鄰接點 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 采用鄰接表存儲結構，編寫一個判別無向圖中任意給定的兩個頂點之間是否存在一條長度為k的簡單路徑的算法。實現下列函數：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. */圖的鄰接表以及相關類型、函數和輔助變量定義如下：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 已知有向圖和圖中兩個頂點u和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; 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 試完成求有向圖的強連通分量的算法，并分析算法的時間復雜度。實現下列函數：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. */圖的十字鏈表以及相關類型和輔助變量定義如下：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 *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中求頂點i到頂點j的不含回路的、長度為k的路徑數。 實現下列函數：int SimplePath(MGraph G, int i, int j, int k);/* 求有向圖G的頂點i到j之間長度為k的簡單路徑條數 */圖的鄰接矩陣存儲結構的類型定義如下：typedef enum DG,DN,AG,AN GraphKind; / 有向圖,有向網,無向圖,無向網typedef struct VRType adj; / 頂點關系類型。對無權圖，用1(是)或0(否)表示相鄰否； / 對帶權圖，則為權值類型 InfoType *info; / 該弧相關信息的指針(可無)ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef stru