第七章　图　题解

核心提示：第七章 图 7.14 Status Build_AdjList(ALGraph &G)/*输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表{ InitALGraph(G); scanf("%d",&v); if(v<0) return ERROR; /*顶点数不能为负 G.vex

　　　　　　　　　　　　　　　　　　　　第七章 图
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;