第7章 图.doc

第7章图

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

//本题中的图G均为有向无权图,其余情况容易由此写出
Status Insert_Vex(MGraph &G, char v)//在邻接矩阵表示的图G上插入顶点v
{
  if(+1)>MAX_VERTEX_NUM return INFEASIBLE;
  [++]=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(![i][j].adj)
  {
    [i][j].adj=1;
    ++;
  }
  return OK;
}//Insert_Arc
Status Delete_Vex(MGraph &G,char v)//在邻接矩阵表示的图G上删除顶点v
{
  n=;
  if((m=LocateVex(G,v))<0) return ERROR;
  [m]<->[n]; //将待删除顶点交换到最后一个顶点
  for(i=0;i<n;i++)
  {
    [i][m]=[i][n];
    [m][i]=[n][i]; //将边的关系随之交换
  }
  [m][m].adj=0;
  --;
  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([i][j].adj)
  {
    [i][j].adj=0;
    --;
  }
  return OK;
}//Delete_Arc

//为节省篇幅,.
Status Insert_Arc(ALGraph &G,char v,char w)//在邻接表表示的图G上插入边(v,w)
{
  if((i=LocateVex