1-105.c

1.7.1 图的邻接矩阵存储表示 311 范例1-102 图的邻接矩阵存储表示 ∷相关函数：CreateFAG函数 CreateDG函数 1.7.2 图的邻接表存储表示 324 范例1-10

  i=LocateVex(*G,v); /* i为待删除顶点的序号 */
  if(i<0)
    return ERROR;
  for(j=0;j<(*G).vexnum;j++) /* 删除与顶点v相连的边(如果有的话) */
  {
    if(j==i)
      continue;
    strcpy(w,*GetVex(*G,j)); /* w是第j个顶点的值 */
    DeleteArc(G,v,w);
  }
  for(j=i+1;j<(*G).vexnum;j++) /* 排在顶点v后面的顶点的序号减1 */
    (*G).adjmulist[j-1]=(*G).adjmulist[j];
  (*G).vexnum--; /* 顶点数减1 */
  for(j=i;j<(*G).vexnum;j++) /* 修改顶点的序号 */
  {
    p=(*G).adjmulist[j].firstedge;
    if(p)
    {
      if(p->ivex==j+1)
      {
        p->ivex--;
        p=p->ilink;
      }
      else
      {
        p->jvex--;
        p=p->jlink;
      }
    }
  }
  return OK;
}
void DestroyGraph(AMLGraph *G)
{
  int i;
  for(i=(*G).vexnum-1;i>=0;i--)
    DeleteVex(G,(*G).adjmulist[i].data);
}
Status InsertArc(AMLGraph *G,VertexType v,VertexType w)
{ /* 初始条件: 无向图G存在,v和W是G中两个顶点 */
  /* 操作结果: 在G中增添弧<v,w> */
  int i,j,l,IncInfo;
  char s[MAX_INFO];
  EBox *p;
  i=LocateVex(*G,v); /* 一端 */
  j=LocateVex(*G,w); /* 另一端 */
  if(i<0||j<0)
    return ERROR;
  p=(EBox*)malloc(sizeof(EBox));
  p->mark=unvisited;
  p->ivex=i;
  p->jvex=j;
  p->info=NULL;
  p->ilink=(*G).adjmulist[i].firstedge; /* 插在表头 */
  (*G).adjmulist[i].firstedge=p;
  p->jlink=(*G).adjmulist[j].firstedge; /* 插在表头 */
  (*G).adjmulist[j].firstedge=p;
  printf("该边是否有相关信息(1:有 0:无): ");
  scanf("%d%*c",&IncInfo); /* 吃掉回车符 */
  if(IncInfo) /* 边有相关信息 */
  {
    printf("请输入该边的相关信息(<%d个字符)：",MAX_INFO);
    gets(s);
    l=strlen(s);
    if(l)
    {
      p->info=(char*)malloc((l+1)*sizeof(char));
      strcpy(p->info,s);
    }
  }
  (*G).edgenum++;
  return OK;
}
Boolean visite[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */
Status(*VisitFunc)(VertexType v);
void DFS(AMLGraph G,int v)
{
  int j;
  EBox *p;
  VisitFunc(G.adjmulist[v].data);
  visite[v]=TRUE;
  p=G.adjmulist[v].firstedge;
  while(p)
  {
    j=p->ivex==v?p->jvex:p->ivex;
    if(!visite[j])
      DFS(G,j);
    p=p->ivex==v?p->ilink:p->jlink;
  }
}
void DFSTraverse(AMLGraph G,Status(*visit)(VertexType))
{ /* 初始条件: 图G存在,Visit是顶点的应用函数。*/
  /* 操作结果: 从第1个顶点起,深度优先遍历图G,并对每个顶点调用函数Visit */
  /*           一次且仅一次。一旦Visit()失败,则操作失败 */
  int v;
  VisitFunc=visit;
  for(v=0;v<G.vexnum;v++)
    visite[v]=FALSE;
  for(v=0;v<G.vexnum;v++)
    if(!visite[v])
      DFS(G,v);
  printf("\n");
}
typedef int QElemType; /* 队列类型 */
typedef struct QNode
{
  QElemType data;
  struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
  QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;
Status InitQueue(LinkQueue *Q)
{ /* 构造一个空队列Q */
  (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));
  if(!(*Q).front)
    exit(OVERFLOW);
  (*Q).front->next=NULL;
  return OK;
}
Status QueueEmpty(LinkQueue Q)
{ /* 若Q为空队列,则返回TRUE,否则返回FALSE */
  if(Q.front==Q.rear)
    return TRUE;
  else
    return FALSE;
}
Status EnQueue(LinkQueue *Q,QElemType e)
{ /* 插入元素e为Q的新的队尾元素 */
  QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
  if(!p) /* 存储分配失败 */
    exit(OVERFLOW);
  p->data=e;
  p->next=NULL;
  (*Q).rear->next=p;
  (*Q).rear=p;
  return OK;
}
Status DeQueue(LinkQueue *Q,QElemType *e)
{ /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
  QueuePtr p;
  if((*Q).front==(*Q).rear)
    return ERROR;
  p=(*Q).front->next;
  *e=p->data;
  (*Q).front->next=p->next;
  if((*Q).rear==p)
    (*Q).rear=(*Q).front;
  free(p);
  return OK;
}
void BFSTraverse(AMLGraph G,Status(*Visit)(VertexType))
{ /* 初始条件: 图G存在,Visit是顶点的应用函数。*/
  /* 操作结果: 从第1个顶点起,按广度优先非递归遍历图G,并对每个顶点调用函数 */
  /*           Visit一次且仅一次。一旦Visit()失败,则操作失败。 */
  /*           使用辅助队列Q和访问标志数组visite */
  int v,u,w;
  VertexType w1,u1;
  LinkQueue Q;
  for(v=0;v<G.vexnum;v++)
    visite[v]=FALSE; /* 置初值 */
  InitQueue(&Q); /* 置空的辅助队列Q */
  for(v=0;v<G.vexnum;v++)
    if(!visite[v]) /* v尚未访问 */
    {
      visite[v]=TRUE; /* 设置访问标志为TRUE(已访问) */
      Visit(G.adjmulist[v].data);
      EnQueue(&Q,v); /* v入队列 */
      while(!QueueEmpty(Q)) /* 队列不空 */
      {
        DeQueue(&Q,&u); /* 队头元素出队并置为u */
        strcpy(u1,*GetVex(G,u));
        for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w))))
          if(!visite[w]) /* w为u的尚未访问的邻接顶点的序号 */
          {
            visite[w]=TRUE;
            Visit(G.adjmulist[w].data);
            EnQueue(&Q,w);
          }
      }
    }
  printf("\n");
}
void MarkUnvizited(AMLGraph G)
{ /* 置边的访问标记为未被访问 */
  int i;
  EBox *p;
  for(i=0;i<G.vexnum;i++)
  {
    p=G.adjmulist[i].firstedge;
    while(p)
    {
      p->mark=unvisited;
      if(p->ivex==i)
        p=p->ilink;
      else
        p=p->jlink;
    }
  }
}
void Display(AMLGraph G)
{ /* 输出无向图的邻接多重表G */
  int i;
  EBox *p;
  MarkUnvizited(G); /* 置边的访问标记为未被访问 */
  printf("%d个顶点：\n",G.vexnum);
  for(i=0;i<G.vexnum;++i)
    printf("%s ",G.adjmulist[i].data);
  printf("\n%d条边:\n",G.edgenum);
  for(i=0;i<G.vexnum;i++)
  {
    p=G.adjmulist[i].firstedge;
    while(p)
      if(p->ivex==i) /* 边的i端与该顶点有关 */
      {
        if(!p->mark) /* 只输出一次 */
        {
          printf("%s－%s ",G.adjmulist[i].data,G.adjmulist[p->jvex].data);
          p->mark=visited;
          if(p->info) /* 输出附带信息 */
            printf("相关信息: %s ",p->info);
        }
        p=p->ilink;
      }
      else /* 边的j端与该顶点有关 */
      {
        if(!p->mark) /* 只输出一次 */
        {
          printf("%s－%s ",G.adjmulist[p->ivex].data,G.adjmulist[i].data);
          p->mark=visited;
          if(p->info) /* 输出附带信息 */
            printf("相关信息: %s ",p->info);
        }
        p=p->jlink;
      }
    printf("\n");
  }
}
Status visit(VertexType v)
{
  printf("%s ",v);
  return OK;
}
void main()
{
  int k,n;
  AMLGraph g;
  VertexType v1,v2;
  CreateGraph(&g);
  Display(g);
  printf("修改顶点的值，请输入原值 新值: ");
  scanf("%s%s",v1,v2);
  PutVex(&g,v1,v2);
  printf("插入新顶点，请输入顶点的值: ");
  scanf("%s",v1);
  InsertVex(&g,v1);
  printf("插入与新顶点有关的边，请输入边数: ");
  scanf("%d",&n);
  for(k=0;k<n;k++)
  {
    printf("请输入另一顶点的值: ");
    scanf("%s",v2);
    InsertArc(&g,v1,v2);
  }
  Display(g);
  printf("深度优先搜索的结果:\n");
  DFSTraverse(g,visit);
  printf("广度优先搜索的结果:\n");
  BFSTraverse(g,visit);
  DestroyGraph(&g);
}