/* ======================================== */
/*    程式實例: 8_2_3.c                     */
/*    圖形的多重鄰接鏈表表示法              */
/* ======================================== */
#include <stdlib.h>

struct edge                       /* 圖形邊線結構宣告     */
{
   int vertex1;                   /* 頂點1資料            */
   int vertex2;                   /* 頂點2資料            */
   struct edge *edge1;            /* 頂點1下一邊線        */
   struct edge *edge2;            /* 頂點2下一邊線        */
};
typedef struct edge *nextedge;    /* 圖形的邊線新型態     */

struct node                       /* 圖形頂點結構宣告     */
{
   int vertex;                    /* 頂點資料             */
   struct edge *edge;             /* 頂點下一邊線         */
};
typedef struct node *graph;       /* 圖形的結構新型態     */
struct node head[6];              /* 圖形頂點結構數組     */

/* ---------------------------------------- */
/*  建立圖形                                */
/* ---------------------------------------- */
void creategraph(int *node,int num)
{
   nextedge newnode;              /* 新邊線指標           */
   nextedge previous;             /* 前一邊線指標         */
   nextedge ptr;                  /* 目前邊線指標         */
   int from;                      /* 邊線的起點           */
   int to;                        /* 邊線的終點           */
   int i;

   for ( i = 0; i < num; i++ )    /* 讀取邊線的回路       */
   {
      from = node[i*2];           /* 邊線的起點           */
      to = node[i*2+1];           /* 邊線的終點           */
      /* 建立新邊線記憶體 */
      newnode = ( nextedge ) malloc(sizeof(struct edge));
      newnode->vertex1 = from;    /* 建立頂點內容         */
      newnode->vertex2 = to;      /* 建立頂點內容         */
      newnode->edge1 = NULL;      /* 設定指標初值         */
      newnode->edge2 = NULL;      /* 設定指標初值         */
      previous = NULL;            /* 前一邊線指標         */
      ptr = head[from].edge;      /* 目前邊線指標         */
      while ( ptr != NULL )       /* 遍歷到最后邊線       */
      {
         previous = ptr;          /* 保留前一邊線         */
         if ( ptr->vertex1 == from )  /* 決定走的邊線     */
            ptr = ptr->edge1;     /* 下一邊線             */
         else
            ptr = ptr->edge2;     /* 下一邊線             */
      }
      if ( previous == NULL )
         head[from].edge = newnode;   /* 設定頂點邊線指標 */
      else
         if ( previous->vertex1 == from ) /* 決定走的邊線 */
            previous->edge1 = newnode;    /* 連接下一邊線 */
         else
            previous->edge2 = newnode;    /* 連接下一邊線 */
      previous = NULL;                    /* 前一邊線指標 */
      ptr = head[to].edge;                /* 目前邊線指標 */
      while ( ptr != NULL )       /* 遍歷到最后邊線       */
      {
         previous = ptr;          /* 保留前一邊線         */
         if ( ptr->vertex1 == to )  /* 決定走的邊線       */
            ptr = ptr->edge1;     /* 下一邊線             */
         else
            ptr = ptr->edge2;     /* 下一邊線             */
      }
      if ( previous == NULL )
         head[to].edge = newnode; /* 設定頂點邊線指標     */
      else
         if ( previous->vertex1 == to ) /* 決定走的邊線   */
            previous->edge1 = newnode;  /* 連接下一邊線   */
         else
            previous->edge2 = newnode;  /* 連接下一邊線   */
   }
}

/* ---------------------------------------- */
/*  主程式: 建立圖形后,將邊線列印出.        */
/* ---------------------------------------- */
void main()
{
   nextedge ptr;
   int node[6][2] = {  {1, 2},    /* 邊線數組             */
                       {1, 3},
                       {2, 3},
                       {2, 4},
                       {3, 5},
                       {4, 5}, };
   int i;

   for ( i = 1; i <= 5; i++ )
   {
      head[i].vertex = i;         /* 設定頂點值           */
      head[i].edge = NULL;        /* 清除圖形指標         */
   }
   creategraph(node,6);           /* 建立圖形             */
   printf("圖形的多重鄰接鏈表內容:\n");
   for ( i = 1; i <= 5; i++ )
   {
      printf("頂點%d =>",head[i].vertex); /* 頂點值       */
      ptr = head[i].edge;                 /* 邊線位置     */
      while ( ptr != NULL )       /* 遍歷至鏈表尾         */
      {
         /* 印出邊線 */
         printf("(%d,%d)",ptr->vertex1,ptr->vertex2);
         /* 決定下一邊線指標 */
         if ( head[i].vertex == ptr->vertex1 )
            ptr = ptr->edge1;     /* 下一個邊線           */
         else
            ptr = ptr->edge2;     /* 下一個邊線           */
      }
      printf("\n");               /* 換行                 */
   }
}