图的邻接表的创建

图的元素有这么几点：顶点数目，顶点信息，弧的数目，弧的信息，以及图的信息。在矩阵表示的时候，弧是较为容易确定的------两个顶点之间，也就是一个二维指针指向的是0还是不是0,或者是无穷大还是有值，通过这些来判断弧的存在。但是在邻接表中，就要用链表的特征：采用指针将图表示出来。 在邻接表中，要对途中的每一个顶点建立一个单链表。

在严版的《数据结构》中，对于每个结点是这么定义的： 里面包含三部分的信息： 包括与顶点邻接的点在图中的位置，下一条弧的结点，以及包括弧的信息，包括弧的权值等信息。  于是她定义了这样的一个数据结构：

typedef struct ArcNode
{
  int adjvex; /* 该弧所指向的顶点的位置 */
  struct ArcNode *nextarc; /* 指向下一条弧的指针 */
  InfoType *info; /* 网的权值指针） */
}ArcNode; /* 表结点 */

用来包含所说的弧的信息。除此之外，还应当包括图里面的其他元素：顶点数目，顶点信息，弧的数目，弧的信息，以及图的信息

typedef struct
{
  VertexType data; /* 顶点信息 */
  ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针 */
}VNode,AdjList[MAX_VERTEX_NUM]; /* 头结点 */

 

 

typedef struct
{
  AdjList vertices;
  int vexnum,arcnum; /* 图的当前顶点数和弧数 */
  int kind; /* 图的种类标志 */
}ALGraph;

其实，我们可以发现，作者是将结点和他连接的弧封装到了一起进行定义： 一个顶点包含的信息应该有：这个顶点的信息，以及和他相连的弧的信息。

利用邻接表创建一个图的过程就是让ALGRAPH都有值的过程。

Status CreateGraph(ALGraph *G)
{ /* 采用邻接表存储结构,构造没有相关信息的图G*/
  int i,j,k;
  int w; /* 权值 */
  VertexType va,vb;
  ArcNode *p;
  printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
  scanf("%d",&(*G).kind);
  printf("请输入图的顶点数,边数: ");
  scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);  / 图的边数和顶点数。
  printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);

 

  for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */ //每个顶点都赋值。同时每个顶点都有一个头。
  {
    scanf("%s",(*G).vertices[i].data);  //////顶点的值
    (*G).vertices[i].firstarc=NULL;      //顶点相连的弧的情况暂时未知，暂时设定为NULL。
  }
  

 

if((*G).kind==1||(*G).kind==3) /* 网 */
    printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n");
  else /* 图 */
    printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n");
  for(k=0;k<(*G).arcnum;++k) /* 构造表结点链表 */
  {
    if((*G).kind==1||(*G).kind==3) /* 网 */
      scanf("%d%s%s",&w,va,vb);
    else /* 图 */
      scanf("%s%s",va,vb);
    i=LocateVex(*G,va); /* 弧尾 */    //弧尾是我们要创建的结点，它来指向j结点。
    j=LocateVex(*G,vb); /* 弧头 */
    p=(ArcNode*)malloc(sizeof(ArcNode));   //这个新建的p实际上是描述的i，但是
    p->adjvex=j;                           //这个位置赋予的j的值是表明与i邻接的点j在图中的位置。
    if((*G).kind==1||(*G).kind==3) /* 网 */
    {
      p->info=(int *)malloc(sizeof(int));
      *(p->info)=w;
    }
    else
      p->info=NULL; /* 图 */

每一个顶点信息里面都存储着与他连着的弧的信息。刚开始初始化为NULL。当有一个顶点成为弧尾的时候，这条弧就成了他的信息。
因此，这个顶点的next要指向现在的firstarc：因为这表明这个顶点曾经做过弧尾了，已经有别的弧依附于他了。
没有关系，让现在的这条新的弧指向原先的那个弧，然后自己再成为这个顶点依附的弧。以前依附的就在我后面吧！

 

    p->nextarc=(*G).vertices[i].firstarc; /* 插在表头 */   //实际上是一种头插法?可以理解为栈的结构，先进后出？
    (*G).vertices[i].firstarc=p;    //后建的放在链表的第一个位置。 
    if((*G).kind>=2) /* 无向图或网,产生第二个表结点 */
    {
      p=(ArcNode*)malloc(sizeof(ArcNode));
      p->adjvex=i;
      if((*G).kind==3) /* 无向网 */
      {
        p->info=(int*)malloc(sizeof(int));
        *(p->info)=w;
      }
      else
        p->info=NULL; /* 无向图 */
      p->nextarc=(*G).vertices[j].firstarc; /* 插在表头 */
      (*G).vertices[j].firstarc=p;
    }
  }
  return OK;
}

我们可以发现，如果一个顶点没有入度，也就是没成为弧尾过的话，他顶点信息里面是没有关于弧的信息的。