数据结构（C语言版）课后习题答案

for(i=0;i

G.arcs[m]=G.arcs[n];

G.arcs[m]=G.arcs[n]; //将边的关系随之交换 }

G.arcs[m][m].adj=0; G.vexnum--; return OK; }//Delete_Vex

分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随着大量元素的移动,时间复杂度也会大大增加。

③ 增加一条边

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

if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(i==j) return ERROR; if(!G.arcs[j].adj) {

G.arcs[j].adj=1; G.arcnum++; }

return OK; }//Insert_Arc

④ 删除一条边

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

if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(G.arcs[j].adj) {

G.arcs[j].adj=0; G.arcnum--; }

return OK; }//Delete_Arc

XLIX

以邻接表作为存储结构，本题只给出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=new ArcNode;

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

if(!G.vertices.firstarc) G.vertices.firstarc=p; else {

for(q=G.vertices.firstarc;q->q->nextarc;q=q->nextarc) if(q->adjvex==j) return ERROR; //边已经存在 q->nextarc=p; }

G.arcnum++; return OK; }//Insert_Arc

（2）一个连通图采用邻接表作为存储结构，设计一个算法，实现从顶点v出发的深度优先遍历的非递归过程。

[算法描述]

Void DFSn(Graph G,int v)

{ //从第v个顶点出发非递归实现深度优先遍历图G

Stack s; SetEmpty(s); Push(s,v);

While(!StackEmpty(s))

{ //栈空时第v个顶点所在的连通分量已遍历完

Pop(s,k);

If(!visited[k]) { { }

L

visited[k]=TRUE;

VisitFunc(k); //访问第k个顶点 //将第k个顶点的所有邻接点进栈

if(!visited[w]&&w!=GetTop(s)) Push(s,w); //图中有环时w==GetTop(s)

for(w=FirstAdjVex(G,k);w;w=NextAdjVex(G,k,w))