严蔚敏《数据结构（c语言版）习题集》全答案(10)

for(i=0;i

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

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

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

分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随着大量元素的移动,时间复杂度也会大大增加. 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[i][j].adj) {

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

return OK; }//Delete_Arc 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(!G.vertices[i].firstarc) G.vertices[i].firstarc=p; else {

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

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

//为节省篇幅,本题只给出较为复杂的Delete_Vex算法.其余算法请自行写出. Status Delete_Vex(OLGraph &G,char v)//在十字链表表示的图G上删除顶点v {

if((m=LocateVex(G,v))<0) return ERROR; n=G.vexnum;

for(i=0;i

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

q=G.xlist[i].firstin;

G.xlist[i].firstin=q->hlink; free(q);G.arcnum--; }

else //否则 {

for(p=G.xlist[i].firstin;p&&p->hlink->tailvex!=m;p=p->hlink); if(p) {

q=p->hlink;

p->hlink=q->hlink; free(q);G.arcnum--; }

}//else }//for

for(i=0;i

if(G.xlist[i].firstout->headvex==m) //如果待删除的边是尾链上的第一个结点 {

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

for(i=m;i

G.xlist[i]=G.xlist[i+1]; //修改表头向量 for(p=G.xlist[i].firstin;p;p=p->hlink) p->headvex--;

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((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(G.adjmulist[i].firstedge->jvex==j)

G.adjmulist[i].firstedge=G.adjmulist[i].firstedge->ilink; else {

for(p=G.adjmulist[i].firstedge;p&&p->ilink->jvex!=j;p=p->ilink); if (!p) return ERROR; //未找到 p->ilink=p->ilink->ilink; } //在i链表中删除该边

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

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

for(p=G.adjmulist[j].firstedge;p&&p->jlink->ivex!=i;p=p->jlink); if (!p) return ERROR; //未找到 q=p->jlink;

p->jlink=q->jlink; free(q);

} //在i链表中删除该边 G.arcnum--; return OK; }//Delete_Arc 7.19

Status Build_AdjMulist(AMLGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接多重表 {

InitAMLGraph(G); scanf(\

if(v<0) return ERROR; //顶点数不能为负 G.vexnum=v; scanf(%d\

if(a<0) return ERROR; //边数不能为负 G.arcnum=a;

for(m=0;m

G.adjmulist[m].data=getchar(); //输入各顶点的符号 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=(EBox*)malloc(sizeof(EBox)); p->ivex=i;p->jvex=j;

p->ilink=NULL;p->jlink=NULL; //边结点赋初值

if(!G.adjmulist[i].firstedge) G.adjmulist[i].firstedge=p; else {

q=G.adjmulist[i].firstedge; while(q) {

r=q;

if(q->ivex==i) q=q->ilink; else q=q->jlink; }

if(r->ivex==i) r->ilink=p;//注意i值既可能出现在边结点的ivex域中, else r->jlink=p; //又可能出现在边结点的jvex域中 }//else //插入i链表尾部

if(!G.adjmulist[j].firstedge) G.adjmulist[j].firstedge=p; else {

q=G.adjmulist[i].firstedge; while(q) {

r=q;

if(q->jvex==j) q=q->jlink; else q=q->ilnk; }

if(r->jvex==j) r->jlink=p; else r->ilink=p;

}//else //插入j链表尾部 }//for return OK;

}//Build_AdjList 7.20

int Pass_MGraph(MGraph G)//判断一个邻接矩阵存储的有向图是不是可传递的,是则返回1,否则返回0 {

for(x=0;x

for(z=0;z

if(z!=x&&G.arcs[y][z]&&!G.arcs[x][z]) return 0;//图不可传递的条件 }//if return 1; }//Pass_MGraph

分析:本算法的时间复杂度大概是O(n^2*d). 7.21

int Pass_ALGraph(ALGraph G)//判断一个邻接表存储的有向图是不是可传递的,是则返回1,否则返回0 {

for(x=0;x

for(p=G.vertices[x].firstarc;p;p=p->nextarc) {

y=p->adjvex;

for(q=G.vertices[y].firstarc;q;q=q->nextarc) {

z=q->adjvex;

if(z!=x&&!is_adj(G,x,z)) return 0; }//for }//for

}//Pass_ALGraph

int is_adj(ALGraph G,int m,int n)//判断有向图G中是否存在边(m,n),是则返回1,否则返回0 {

for(p=G.vertices[m].firstarc;p;p=p->nextarc) if(p->adjvex==n) return 1;

return 0; }//is_adj 7.22

int visited[MAXSIZE]; //指示顶点是否在当前路径上

int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0 {

if(i==j) return 1; //i就是j else {

visited[i]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

k=p->adjvex;

if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径 }//for }//else

}//exist_path_DFS 7.23

int exist_path_BFS(ALGraph G,int i,int j)//广度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0 {

int visited[MAXSIZE]; InitQueue(Q); EnQueue(Q,i);

while(!QueueEmpty(Q)) {

DeQueue(Q,u); visited[u]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

k=p->adjvex;

if(k==j) return 1;

if(!visited[k]) EnQueue(Q,k); }//for }//while return 0;

}//exist_path_BFS 7.24

void STraverse_Nonrecursive(Graph G)//非递归遍历强连通图G {

int visited[MAXSIZE]; InitStack(S);

Push(S,GetVex(S,1)); //将第一个顶点入栈 visit(1); visited=1;

while(!StackEmpty(S)) {

while(Gettop(S,i)&&i) {

j=FirstAdjVex(G,i); if(j&&!visited[j]) {

visit(j);

visited[j]=1;

Push(S,j); //向左走到尽头 }

}//while

if(!StackEmpty(S)) {

Pop(S,j); Gettop(S,i);

k=NextAdjVex(G,i,j); //向右走一步 if(k&&!visited[k]) {

visit(k);

visited[k]=1; Push(S,k);

} }//if }//while

}//Straverse_Nonrecursive

分析:本算法的基本思想与二叉树的先序遍历非递归算法相同,请参考6.37.由于是强连通图,所以从第一个结点出发一定能够访问到所有结点. 7.25 见书后解答. 7.26

Status TopoNo(ALGraph G)//按照题目要求顺序重排有向图中的顶点 {

int new[MAXSIZE],indegree[MAXSIZE]; //储存结点的新序号 n=G.vexnum;

FindInDegree(G,indegree); InitStack(S);

for(i=1;i

if(!indegree[i]) Push(S,i); //零入度结点入栈 count=0;

while(!StackEmpty(S)) {

Pop(S,i);

new[i]=n--; //记录结点的拓扑逆序序号 count++;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

k=p->adjvex;

if(!(--indegree[k])) Push(S,k); }//for }//while

if(count

for(i=1;i<=n;i++) printf(\ return OK; }//TopoNo

分析:只要按拓扑逆序对顶点编号,就可以使邻接矩阵成为下三角矩阵. 7.27

int visited[MAXSIZE];

int exist_path_len(ALGraph G,int i,int j,int k)//判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径 {

if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求 else if(k>0) {

visited[i]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

l=p->adjvex; if(!visited[l])

if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一 }//for

visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中 }//else

return 0; //没找到 }//exist_path_len 7.28

int path[MAXSIZE],visited[MAXSIZE]; //暂存遍历过程中的路径

int Find_All_Path(ALGraph G,int u,int v,int k)//求有向图G中顶点u到v之间的所有简单路径,k表示当前路径长度 {

path[k]=u; //加入当前路径中 visited[u]=1;

if(u==v) //找到了一条简单路径 {

printf(\

for(i=0;path[i];i++) printf(\打印输出 }