发布时间 : 星期三 文章数据结构作业系统_第七章答案更新完毕开始阅读d89803a27f21af45b307e87101f69e314232faf8
} 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 &path, int &i,int &d,VertexType A[]) { int j,k,l,m,n; ArcNode *p; j=LocateVex(g,sv); visited[j]=1; A[d++]=sv; if(sv==tv){m=0; for(n=0;n for(p=g.vertices[j].firstarc;p;p=p->nextarc){l=p->adjvex; if(!visited[l]) AllPath2(g,g.vertices[l].data,tv,path,i,d,A);}visited[j]=0; d--;}void AllPath(ALGraph g, VertexType sv, VertexType tv, 9 / 14 StrARR &path, int &i) /* Get all the paths from vertex sv to tv, save them */ /* Return the number of path using i*/{int d=0,j,l; VertexType A[MAX_VERTEX_NUM],B[MAX_VERTEX_NUM]; for(l=0;l<5;l++){strcpy(B,path[l]); for(j=0;j depath(path[l],B[j]);}AllPath2(g,sv,tv,path,i,d,A);} 7.31③试完成求有向图的强连通分量的算法，并分析算法的时间复杂度。 实现下列函数： void StronglyConnected(OLGraph dig, StrARR &scc, int &n); /* and put the ith into scc[i] which is a string.*/ 图的十字链表以及相关类型和辅助变量定义如下： Status visited[MAX_VERTEX_NUM]; int finished[MAX_VERTEX_NUM]; typedef char StrARR[MAX_VERTEX_NUM][MAX_VERTEX_NUM+1]; //记录各强连通分量typedef struct ArcBox { int tailvex,headvex; struct ArcBox *hlink,*tlink; } ArcBox; typedef struct VexNode { VertexType data; ArcBox*firstin,*firstout; 10 / 14 } VexNode; typedef struct { VexNode xlist[MAX_VERTEX_NUM]; } 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) /* and put the ith into scc[i] which is a string.*/{int i,k=0,v; count=0; for(v=0;v for(v=0;v for(i=dig.vexnum-1;i>=0;i--){v=finished[i]; if(!visited[v]){DFS2(dig,v,scc,n,k); n++;}}}void DFS1(OLGraph dig,int v){int w; ArcBox *p; visited[v]=1; for(p=dig.xlist[v].firstout;p;p=p->tlink) 11 / 14 {w=p->headvex; if(!visited[w]) DFS1(dig,w);}finished[count++]=v;}void DFS2(OLGraph dig,int v,StrARR &scc,int j,int k){int w; ArcBox *p; visited[v]=1; scc[j][k++]=dig.xlist[v].data; for(p=dig.xlist[v].firstin;p;p=p->hlink){w=p->tailvex; if(!visited[w]) 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(否)表示相邻否； //对带权图，则为权值类型 12 / 14