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

void Inser-Mgraph (mGraph *G,int k) {int i,j; G->n++;

for(i=G->n;i>k;i--)G->vexs[i]=G->vexs[i-1]; G->cexs[k]=getchar(); for(i=G->n;i>k;i--)

{ for(j=G->n;j>k;j--)

G->e[i][j]=G->e[i-1][j-1]; G->e[i][j]=0;

for(j=k-1;j>=0;j--)

G->e[i][j]=G->e[i-1][j]; }

for(j=G->n;j>=0;j--)G->e[i][j]=0; for(i=k-1;i>=0;j--) { for(j=g->n;j>k;j--)

G->e[i][j]=G->e[i][j-1]; G->e[i][j]=0 } }

⑵插入一条边 ① 邻接表

InsertLAGraph (ALGraph *G,int m,INT n) { EdgeNode *E;

EdgeNode *sm=new EdgeNode; EdgeNode *sn=new Edgenode; Sm->adjvex=n;sm->next=Null; Sn->adjvex=m;sn->next=Null;

for(E=G->adjlist[m].firstedge;E!=NULL;E=E->next) { }

E=sm;

for(E=G->adjlist[n].firstedge;E!=NULL;E=E->next) { } E=sn;

}

② 邻接矩阵

void InsertLMGraph(mGraph *G,int m,int n) { G->e[m][n]=1;

}

（3）删除某结点 ① 邻接表

void DelVALGraph(ALGraph *g,int k) { int I; G->n--;

EdgeNode *e *s;

for(E=G->adjlist[k].firstdge;E!=NULL;E=E->next)

{ for (s=G->adjlist[E->adjvxe].firstedge;E!=NULL;E->E->next) if(s->adjvex==k) {s=s->next;break;} }

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

{ G->adjlist[i].vertex=G->adjlist[i+1].vextex;

G->adjlist[i].first[i].firstedge=G->adjlist[i+1].firstedge;

}

}

② 邻接矩阵

void delvMGraph(mGraph *G,int k) {int i,j; G->n--;

for(i=k;i<=g->n;i++) G->vexs[i]=G->vexs[i+1]; for(i=0;i

for(j=k;j<=n;j++) G->e[i][j]=G->e[i][j];

for(i=k;i<=G->n;i++)

{for(j=0;je[i][j]=G->e[i+1][j]; for(j=k;j<=n;j++) G->e[i][j]=G->e[i+1][j]; } }

(4)删除某条边 ① 邻接表

void dellALGraph(ALGraph *G,int m,int n) {EdgeNode *s;

for(S=G->adjlist[m].firstedge; s->adjvex!=k;s=s->next) s=s->next; for(s=G->adjlist[n].firstedge;

s->adjvex!=k;s=s->next) s=s->next;

}

②邻接矩阵

void InsertLMGraph(mGraph *G,int m,int n) {G->e[m][n]=0; G->e[n][m]=0; }

7.17 下面的伪代码是一个广度优先搜索算法,试以图7.29中的V4为源点执行该算法,请回答下述问题:

(1) 对图中顶点Vn+1,它需要入队多少次?它被重复访问多少次? (2) 若要避免重复访问同一个顶点的错误,应如何修改此算法?

Void BFS(ALGraph *G,int k)

{//以下省略局部变量的说明,visited各分量初值为假

InitQueue(&Q); //置空队列 EnQueue(&Q,k); //k入队 While(!QueueEmpty(&Q))

{I=DeQueue(&Q); //vi出队

visited[I]=true //置访问标记// printf(“%c”,G->adjilist[i],vertes); //访问j

for(p=G->adjilist[i],firstedge;p;p=p->adjves=j)//依次搜索vi的邻接点vj (不妨设p->adjves=j)

if(!Visited[p->adjves]) //若vj未被访问 EnQueue(&Q,p->adjves); //vj入队 } //endwhile } //BFS

解：

对图中顶点vn+1,它需入队n次？它被重复访问n-1次。 若要避免重复访问同一个顶点的错误，应修改算法如下： Void BFS(ALGraph*G,int K)

{ /*以下省略局部变量得说明，visited各分量初值为假*/ InitQueue(&Q); /*置空队列*/

EnQueue(&Q,k); /*k队列*/ While(!QueueEmpty(&Q))

{I=DeQueue(&Q); /*vi出队*/ visited[I]=true /*置访问标记*/ printf(“%c”,G->adjilist[i],vertes);/*访问vi*/

for(p=G->adjlist[i],firstedge;p;p->adjves=j)

/*依次搜索vi的邻接点vj（不妨设p->adjves=j）*/ if(!Vvisit[p->adjves]) /*若vj未访问过*/ {

EnQueue(&Q,p->adjves); /*/vj入队*/ Visited[p->adjvex]=TRUE; }

} /*endwhile*/ } /*BFS*/

7.18 试以邻接表和邻接矩阵为存储结构，分别写出基于DFS和BFS遍历的算法来判别顶点vi和vj(I<>j)之间是否有路径。 解：

/*基于邻接表方式*/ /*所有数据类型*/ #define maxvn 10 typedef struct node { int vertex; int vertex;

setuct node *list; } vertexNode

vertexNode *head[maxvn];

bool JUDGE(vertexNode *adjl[maxvn],int n,int j);

/*深度优先搜索判别n个顶点的有向图中顶点I到顶点j是否存在路径*/ { int stack[maxvn]; bool visit[maxvm]; int top,k; vertexNODE *p; bool yes;

for(k=1;k<=n;k++) visit[k]=false; top=1;

stack[top]=i; visit[i]=True; yes=false; do{

p=adjl[stack[top]];

while(!p=NULL&&visit[p->vertex]p=p->link); if(p==NULL)

top=top-1; /*p之后无邻接结点，退栈*/ else

{i=p->vertex; /*p指向的顶点未访问*/ if(i==j) yes=true; else

{ visit[i]=true; top=top+1; stack[top]=i;

}

}while(top1=0&&!yes); return(yes); }

7．19 试分别写出求DFS和BFS生成树（或生成森林）的算法，要求打印出所有的树边。 解：

①/*以Vi为树根，对邻接矩阵表示的图G进行DFS搜索*/

void DFSM(Mgraph *G,int ) { int j;

printf(“visit vertex:%c”,G->vexs[i]); visitcd[i]=True; for(j=0;j<=G->n;j++)

if(G->edges[i][j]==1&&!visit[j]) { print(“edye:%d?%d\\n”,i,j); DESM(G,j); } }

②/*以VI为树根，对邻接矩阵表示的图G进行DFS搜索*/ void DFSM(Mgraph *G,int k) { int i,j;

SETNULL(Q); /*置空队Q*/ Printf(‘%/“，G.vexs[k]);

Visited[k]=True; /*标志Vk+1已经访问过*/ ENQUEUE(Q,k); /* 已经访问过的顶点如队列*/ …… 此处隐藏：3259字，全部文档内容请下载后查看。喜欢就下载吧 ……