第七章 图.txt

严蔚敏《数据结构(c语言版)习题集》 参考答案

第七章 图  


7.14

Status Build_AdjList(ALGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表
{
　InitALGraph(G);
　scanf("%d",&v);
　if(v<0) return ERROR; //顶点数不能为负
　G.vexnum=v;
　scanf("%d",&a);
　if(a<0) return ERROR; //边数不能为负
　G.arcnum=a;
　for(m=0;m<v;m++)
　　G.vertices[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=(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);
　　　q->nextarc=p;
　　}
　　p->adjvex=j;p->nextarc=NULL;
　}//while
　return OK;
}//Build_AdjList

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)
{
　if((i=LocateVex(G,v))<0) return ERROR;
　if((j=LocateVex(G,w))<0) return ERROR;
　if(i==j) return ERROR;
　if(!G.arcs[i][j].adj)
　{
　　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]; //将待删除顶点交换到最后一个顶点
　for(i=0;i<n;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<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 //否则
　　{
　　　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<n;i++) //删除所有以v为尾的边
　{
　　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<n;i++) //顺次用结点m之后的顶点取代前一个顶点
　{
　　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("%d",&v);
　if(v<0) return ERROR; //顶点数不能为负
　G.vexnum=v;
　scanf(%d",&a);
　if(a<0) return ERROR; //边数不能为负
　G.arcnum=a;
　for(m=0;m<v;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<G.vexnum;x++)
　　for(y=0;y<G.vexnum;y++)
　　　if(G.arcs[x][y])
　　　{
　　　　for(z=0;z<G.vexnum;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<G.vexnum;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<G.vexnum;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<G.vexnum) return ERROR; //图中存在环
　for(i=1;i<=n;i++) printf("Old No:%d New No:%d\n",i,new[i])
　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("Found one path!\n");
　　for(i=0;path[i];i++) printf("%d",path[i]); //打印输出
　}
　else
　　for(p=G.vertices[u].firstarc;p;p=p->nextarc)
　　{
　　　l=p->adjvex;
　　　if(!visited[l]) Find_All_Path(G,l,v,k+1); //继续寻找
　　}
　visited[u]=0;
　path[k]=0; //回溯
}//Find_All_Path

main()
{
　...
　Find_All_Path(G,u,v,0); //在主函数中初次调用,k值应为0
　...
}//main

7.29

int GetPathNum_Len(ALGraph G,int i,int j,int len)//求邻接表方式存储的有向图G的顶点i到j之间长度为len的简单路径条数
{
　if(i==j&&len==0) return 1; //找到了一条路径,且长度符合要求
　else if(len>0)
　{
　　sum=0; //sum表示通过本结点的路径数
　　visited[i]=1;
　　for(p=G.vertices[i].firstarc;p;p=p->nextarc)
　　{
　　　l=p->adjvex;
　　　if(!visited[l])
　　　　sum+=GetPathNum_Len(G,l,j,len-1)//剩余路径长度减一
　　}//for
　　visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中
　}//else
　return sum;
}//GetPathNum_Len

7.30

int visited[MAXSIZE];
int path[MAXSIZE]; //暂存当前路径
int cycles[MAXSIZE][MAXSIZE]; //储存发现的回路所包含的结点
int thiscycle[MAXSIZE]; //储存当前发现的一个回路
int cycount=0; //已发现的回路个数

void GetAllCycle(ALGraph G)//求有向图中所有的简单回路
{
　for(v=0;v<G.vexnum;v++) visited[v]=0;
　for(v=0;v<G.vexnum;v++)
　　if(!visited[v]) DFS(G,v,0); //深度优先遍历
}//DFSTraverse

void DFS(ALGraph G,int v,int k)//k表示当前结点在路径上的序号