1、精選優(yōu)質(zhì)文檔-傾情為你奉上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 initia

2、led 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 AdjList vertices; int vexnum, a

3、rcnum; ALGraph;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->n

4、extarc) if(p) 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. */* A

5、rray 'visited' 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

6、struct AdjList 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

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

8、->adjvex; 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ù)和輔助變量定義如

9、下：Status visitedMAX_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 &

10、amp;x);Status 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)

11、; while(!StackEmpty(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)之間是否存在一條長度為k的簡單路徑的算法。實(shí)現(xiàn)下列函數(shù)：Status SinglePath

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

13、f 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; ALGraph;int LocateVex(Graph g, VertexType v);void inpath(char *&path, VertexType v); /* Add ver

14、tex 'v' 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 usin

15、g string sp if 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.v

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

17、sing i */圖的鄰接表以及相關(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 AdjLis

18、t vertices; int 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, VertexTy

19、pe tv, StrARR &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)

20、; visitedj=0; 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

21、_NUM; for(l=0;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

22、put the ith into 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;

23、 ArcBox *firstin,*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 connecte

24、d 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;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(OLGra

25、ph dig,int v) 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

26、) w=p->tailvex; if(!visitedw) DFS2(dig,w,scc,j,k); 7.29 試寫一個(gè)算法，在以鄰接矩陣方式存儲(chǔ)的有向圖G中求頂點(diǎn)i到頂點(diǎn)j的不含回路的、長度為k的路徑數(shù)。 實(shí)現(xiàn)下列函數(shù)：int SimplePath(MGraph G, int i, int j, int k);/* 求有向圖G的頂點(diǎn)i到j(luò)之間長度為k的簡單路徑條數(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 struct Adj