严蔚敏《数据结构》教材习题集答案

第七章 图

7.14

Status Build_AdjList(ALGraph &G)//输入有向图的顶点数,边数,顶点信息和边的

信息建立邻接表

{

InitALGraph(G);

scanf("%d",&v);

if(v<0) return ERROR; //顶点数不能为负

for(m=1;m<=a;m++)

{

t=getchar();h=getchar(); //t 为弧尾,h 为弧头

if((i=LocateVex(G,t))<0) return ERROR;

if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到

p=(ArcNode*)malloc(sizeof(ArcNode));

if(!G.vertices.[i].firstarc) G.vertices[i].firstarc=p;

else

{

for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc);

7.15

//本题中的图 G 均为有向无权图,其余情况容易由此写出

Status Insert_Vex(MGraph &G, char v)//在邻接矩阵表示的图 G 上插入顶点 v

{

if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE;

G.vexs[++G.vexnum]=v;

return OK;

}//Insert_Vex

Status Insert_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图 G 上插入边

(v,w)

G.arcs[i][j].adj=1;

G.arcnum++;

}

return OK;

}//Insert_Arc

Status Delete_Vex(MGraph &G,char v)//在邻接矩阵表示的图 G 上删除顶点 v

{

n=G.vexnum;

if((m=LocateVex(G,v))<0) return ERROR;

G.vexs[m]<->G.vexs[n]; //将待删除顶点交换到最后一个顶点

G.vexnum--;

return OK;

}//Delete_Vex

分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随

着大量元素的移动,时间复杂度也会大大增加.

Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图 G 上删除边

{

if((i=LocateVex(G,v))<0) return ERROR;

if((j=LocateVex(G,w))<0) return ERROR;

if(G.arcs[i][j].adj)

7.16

//为节省篇幅,本题只给出 Insert_Arc 算法.其余算法请自行写出.

Status Insert_Arc(ALGraph &G,char v,char w)//在邻接表表示的图 G 上插入边

(v,w)

{

if((i=LocateVex(G,v))<0) return ERROR;

if((j=LocateVex(G,w))<0) return ERROR;

p=(ArcNode*)malloc(sizeof(ArcNode));

p->adjvex=j;p->nextarc=NULL;

{

if(q->adjvex==j) return ERROR; //边已经存在

q->nextarc=p;

}

G.arcnum++;

return OK;

}//Insert_Arc

for(i=0;i<n;i++) //删除所有以 v 为头的边

{

if(G.xlist[i].firstin->tailvex==m) //如果待删除的边是头链上的第一个结点

{

q=G.xlist[i].firstin;

G.xlist[i].firstin=q->hlink;

free(q);G.arcnum--;

}

else //否则

{

p->hlink=q->hlink;

free(q);G.arcnum--;

{

q=G.xlist[i].firstout;

G.xlist[i].firstout=q->tlink;

free(q);G.arcnum--;

}

else //否则

{

for(p=G.xlist[i].firstout;p&&p->tlink->headvex!=m;p=p->tlink);

if(p)

{

q=p->tlink;

p->tlink=q->tlink;

free(q);G.arcnum--;

}

}//else

for(p=G.xlist[i].firstout;p;p=p->tlink)

p->tailvex--; //修改各链中的顶点序号

}

G.vexnum--;

return OK;

}//Delete_Vex

7.18

//为节省篇幅,本题只给出 Delete_Arc 算法.其余算法请自行写出.

Status Delete_Arc(AMLGraph &G,char v,char w)////在邻接多重表表示的图 G 上删

除边(v,w)

if((j=LocateVex(G,w))<0) return ERROR;

if(G.adjmulist[i].firstedge->jvex==j)

if(G.adjmulist[j].firstedge->ivex==i)

G.adjmulist[j].firstedge=G.adjmulist[j].firstedge->jlink;

else

{

q=p->jlink;

p->jlink=q->jlink;

free(q);

} //在 i 链表中删除该边

G.arcnum--;

return OK;

}//Delete_Arc

Status Build_AdjMulist(AMLGraph &G)//输入有向图的顶点数,边数,顶点信息和

边的信息建立邻接多重表

if(v<0) return ERROR; //顶点数不能为负

if(a<0) return ERROR; //边数不能为负

G.arcnum=a;

for(m=0;m<v;m++)

G.adjmulist[m].data=getchar(); //输入各顶点的符号

t=getchar();h=getchar(); //t 为弧尾,h 为弧头

if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到

p->ivex=i;p->jvex=j;