/*

     以数组表示法(邻接矩阵)作为图的存储结构创建图。

 */

 #include <stdio.h>

 #include <stdlib.h>

 #include <string.h>

 #define INFINITY        100000    //最大值

 #define MAX_VERTEX_NUM    20        //最大顶点数

 typedef enum {DG, DN, UDG, UDN} GraphKind; //{有向图，有向网，无向图，无向网}

 typedef int  VRType;

 typedef char VertexType;

 typedef struct{

     char note[];

 }InfoType;

 typedef struct ArcCell{

     VRType adj;        //顶点关系类型：1)对无权图，用1或0表示相邻否；2)对带权图，则为权值类型

     InfoType *info;    //该弧相关信息的指针

 }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

 typedef struct{

     VertexType vexs[MAX_VERTEX_NUM];    //顶点向量

     AdjMatrix arcs;        //邻接矩阵

     int vexnum, arcnum;    //图的当前顶点数和弧数

     GraphKind kind;        //图的种类标志

 }MGraph;

 /*

     若G中存在顶点u，则返回该顶点在图中位置；否则返回-1。

 */

 int LocateVex(MGraph G, VertexType v){

     int i = ;

     for(i=; i<G.vexnum; i++){

         if(G.vexs[i] == v){

             return i;

         }

     }

     return -;

 }

 /*

     采用数组表示法(邻接矩阵)，构造无向网

 */

 int CreateUDN(MGraph *G){

     int i = , j = , k = , IncInfo = ;

     int v1 = , v2 = , w = ;

     char tmp[] = {};

     printf("输入顶点数，弧数，其他信息标志位: ");

     scanf("%d,%d,%d", &G->vexnum, &G->arcnum, &IncInfo);

     for(i=; i<G->vexnum; i++){

         printf("input vexs %d: ", i+);

         memset(tmp, , sizeof(tmp));

         scanf("%s", tmp);

         G->vexs[i] = tmp[];

     }

     for(i=; i<G->vexnum; i++){

         for(j=; j<G->vexnum; j++){

             G->arcs[i][j].adj = INFINITY;

             G->arcs[i][j].info = NULL;

         }

     }

     for(k=; k<G->arcnum; k++){

         printf("输入第%d条弧: 顶点1, 顶点2，权值", k+);

         memset(tmp, , sizeof(tmp));

         scanf("%s", tmp);

         sscanf(tmp, "%c,%c,%d", &v1, &v2, &w);

         i = LocateVex(*G, v1);

         j = LocateVex(*G, v2);

         G->arcs[i][j].adj = w;

         if(IncInfo){

             //

         }

         G->arcs[j][i] = G->arcs[i][j];

     }

     return ;

 }

 /*

     采用数组表示法(邻接矩阵)，构造无向图

 */

 int CreateUDG(MGraph *G)

 {

     int i = , j = , k = , IncInfo = ;

     int v1 = , v2 = , w = ;

     char tmp[] = {};

     printf("输入顶点数，弧数，其他信息标志位: ");

     scanf("%d,%d,%d", &G->vexnum, &G->arcnum, &IncInfo);

     for(i=; i<G->vexnum; i++){

         printf("输入第%d个顶点: ", i+);

         memset(tmp, , sizeof(tmp));

         scanf("%s", tmp);

         G->vexs[i] = tmp[];

     }

     for(i=; i<G->vexnum; i++){

         for(j=; j<G->vexnum; j++){

             G->arcs[i][j].adj = ;

             G->arcs[i][j].info = NULL;

         }

     }

     for(k=; k<G->arcnum; k++){

         printf("输入第%d条弧(顶点1, 顶点2): ", k+);

         memset(tmp, , sizeof(tmp));

         scanf("%s", tmp);

         sscanf(tmp, "%c,%c", &v1, &v2, &w);

         i = LocateVex(*G, v1);

         j = LocateVex(*G, v2);

         G->arcs[i][j].adj = ;

         if(IncInfo){

             //

         }

         G->arcs[j][i] = G->arcs[i][j];

     }

     return ;

 }

 /*

     采用数组表示法(邻接矩阵)，构造图

 */

 int CreateGraph(MGraph *G)

 {

     printf("输入图类型: -有向图(0), -有向网(1), +无向图(2), +无向网(3): ");

     scanf("%d", &G->kind);

     switch(G->kind){

         case DG://构造有向图

         case DN://构造有向网

             printf("还不支持!\n");

             return -;

         case UDG://构造无向图

             return CreateUDG(G);

         case UDN://构造无向网

             return CreateUDN(G);

         default:

             return -;

     }

 }

 /*

     输出图的信息

 */

 void printG(MGraph G)

 {

     if(G.kind == DG){

         printf("类型：有向图；顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);

     }else if(G.kind == DN){

         printf("类型：有向网；顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);

     }else if(G.kind == UDG){

         printf("类型：无向图；顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);

     }else if(G.kind == UDN){

         printf("类型：无向网；顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);

     }

     int i = , j = ;

     printf("\t");

     for(i=; i<G.vexnum; i++){

         printf("%c\t", G.vexs[i]);

     }

     printf("\n");

     for(i=; i<G.vexnum; i++){

         printf("%c\t", G.vexs[i]);

         for(j=; j<G.vexnum; j++){

             if(G.arcs[i][j].adj == INFINITY){

                 printf("INF\t");

             }else{

                 printf("%d\t", G.arcs[i][j].adj);

             }

         }

         printf("\n");

     }

 }

 int main(int argc, char *argv[])

 {

     MGraph G;

     if(CreateGraph(&G) > -)

         printG(G);

     return ;

 }