严蔚敏++数据结构习题集答案(7)

其中k表示第k次迭代运算。A[0][i,j]=A[i,j]. #define MAXVEX 100

void floyd(a,c,n) /*c为已知邻接矩阵，a为待求矩阵，n为源点数*/ int a[MAXVEX][MAXVEX] c[MAXVEX][MAXVEX],n; {int i,j,k;

for(i=1;i<=n;i++) for(j=1;j<=n;j++) a[i][j]=c[i][j];

for(i=1;i<=n;i++) a[i][j]=0; for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++)

if(a[i][k]+a[k][j]

}

7.22以邻接表为存储结构，写一个基于DFS遍历策略的算法，求图中通过某顶点vk的简单回路（若存在）。 解：

算法思想，从给定顶点v4出发进行深度优先搜索，在搜索过程中判断当前访问的顶点是否为v4。若是，则找到一条回路。否则继续搜索。为此设一个顺序栈cycle记录构成回路的顶点序列，把访问顶点的操作改为将当前访问的顶点入栈；相应地，若从某一顶点出发搜索完再回溯，则做退栈操作，同时要求找到的回路的路径应大于2。另外还设置一个found，出值为0，当找到回路后为1。

Void dfscycle (ALGrph *G,int V4) {int i,j,top=0,V=V4,found=0,w; int Visitde[100],cycle[100]; EdgeNode *P; i=1;

cycle[i]=Vi /*从V是开始搜索*/ Visitde[v]==1; P=G[v]->firstedge;

While(p!=NULL!!top>0)&&!found) { while(p!=NULL&&!found)

if(p->adjvex==V4&&i<2)found=1; /*找到回路*/

else if(visited[p->adjvex]==0)p=p->next; /*找到下一个邻接点*/ elst

{w=p->adjvex; /*记下路径，继续搜索*/ visited[w]=1; i++;

cycle[i]=w; top++;

stack[top]=p;

p=G[w]->firstedge; }

if(!found&&top>0) /*沿原路径退回后，另选路径进行搜索*/ { p=attack[top]; top--; p=p->next; i--; }

} /*end while*/

if(found)

{for(j=1;j<=i;j++)

printf(“%d,”,cycle[j]); /*打印回路的顶点序列*/ printf(“%d,\\n”,V); }

else printf(“设有通过点V4的回路！\\n”) }

7．23 写一算法求有向图的所有根（若存在），分析算法的时间复杂度。 解：

算法思想：以有向图的每一个结点为源点对圆进行搜索，若能搜索到每个结点。则该结点为根。否则不是。

Void searchroot （ALGraph *G） { int i;

for(i=0;in;i++) {for(j=0;jn;j++)

visited[j]=false; /*标志向量初始化*/ DPS(G,i); /*以Vi为源点开始DPS搜索*/ } }

void DPS(ALGtaph *G,int i) { int count=0; EdgeNode *P; Visited[i]=true; count ++;

p=G->adjlist[i]->firstedge; while(p)

{if(!Visited[p->adjvex]) DPS(G,p->adjvex); P=p->next; }

if(count==G->n) /*该结点是根结点*/ printf(“%c”,G->adjlist[i]->vertex); }

7．24 改写7.5节的算法print,试输出的从源点到各终点的最短路径是正想。（提示：使用栈暂存路径）。 解：

使用栈暂存路径

void Ptint(PathP,Distance D) { int i,pre; seqstack *S;

s->top=-1 /*置空栈*/ for(i=0;i

{printf(“\\n distanck:%d,Path;”,D[i]);

/*输出终点I的最短距离*/ s->top++;

s->stack[s->top]=i; /*i入栈*/

pre=p[i]; /*栈终点的前趋*/ while(s->top>1)

{printf(“%d”,s->stack[s->top]); /*输出路径*/ s->top--;

} /*end while */

} /*end for*/ }

7.24改写7.5节的算法print，使输出的从源点到各终点的最短路径是正向。（提示：使用栈暂存路径）。

解：

使用栈暂存路径

void Print(PathP,Distance D) { int ,pre;

seqstack *s;

s->top=-1 /*置空栈*/ for(i=0;i

{printf(“\\n distanck:%d,path:”,D[i]);

/*输出终点i的最短距离*/ s->top++;

s->stack[s->top]=i; /*I入栈*/

pre=p[i]; /*栈终点的前趋*/ while(pre!=-1) {s->top++;

s->stack[s->top]=pre; /*路径入栈保存*/ pre=p[pre]; /*继续上溯前趋*/ }

while(s->top>-1)

{printf(“%d”,s->stack[s->top]); /*输出路径*/ s->top--;

} /*end while*/ } /*end for*/ }

7.25 对7.6节的NonSuccFirstTopSort算法，分别以邻接矩阵和邻接表作为存储结构， 写出其具体算法，并分析算法的时间。 解：

① 用逆邻接表作为G的存储结构。 Void NonSuccPirstTopSort(G)

{int outdehree[maxvertexNum]; /*出度向量，Maxvertexnum>=G,n*/ seqstack S,T; /*应将栈中data向量改为int类型*/ int i,j,count=0; Edgenode *P;

for(i=0;i

for(p=G->adjlist[i]->firstedge;p;p->next) /*扫描的入边表*/ outdegree[p->adjvex]++; /*出度为1*/ Initstack(&S); /*置空栈*/ Initstack(&T); for(i=0;in;i++) if(outdegree[i]==0)

push（&S,i） /*出度为零的顶点i入栈 */

while(!stackEmpty(&S)) /*栈非空，即图中有出度为0的顶点*/ {i=pop(&S); push(&T,i); count++;

for(p=G->adjlist[i]->firstedge;P;p=p->next); /*扫描的i入边表*/ {j=p->adjvex; /*j是i的入边的起点*/

outdegree[j]--; /*j的出度减肥。相当于删去边*/ if(!outdegree[i]) /*j无后继*/ push(&S,j); }/*end for*/ } /*end while*/ if(countn)

printf(“\\n The Graph is not a DAG.\\n”); /*图中有环，排序失败*/ else

{while(!stackEmpty(&S)) /*输出拓扑序列*/ {i=po(&T);print(“%d”,G->adjlist[i]->vertex);} } }

②用邻接矩阵作为存储结构。

Void NoSucePirstTopSort(Mgraph *G) {seqstack s,T;

int i,j,count=0; /*用i,j代表Vi,Vj*/

Initstack(&S); Initstack(&T);

for(i=0;in;i++)

for(j=0;jn;j++) if(G->edges[i][j]= =0)

push(&S,i); /*出度为0，入栈*/ while(!sruckEmpty(&S)) { i=po(&S); push(&T,i); count+ +;

for(j=0;j…… 此处隐藏：3005字，全部文档内容请下载后查看。喜欢就下载吧 ……