#include <iostream>
#include "Graph.h"
using namespace std;

int main()
{
MGraph G;
if(CreateGraph(G))
   printf("Sucess CreateGraph!\n");
return 0;
}

Graph.h

//图的邻接矩阵存储表示
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
#define VertexType char
#define VRType int
typedef enum{DG,DN,UDG,UDN} GraphKind;

typedef struct ArcCell
{
VRType adj;//VRType表示顶点关系类型，对无权图，用1或0
//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;

int LocateVex(MGraph G,VertexType u)
{
return u-'A';
}

bool CreateDG(MGraph &G)
{
int i,j,k;
VertexType v1,v2;
printf("Please Input the vexnum and arcnum of the Graph:");
scanf("%d %d",&G.vexnum,&G.arcnum);
printf("Input the vexs of the Graph\n");
for(i=0; i<G.vexnum; i++)
{
   printf("The %d vex:",i+1);
   scanf(" %c",&G.vexs[i]);
}
for(i=0;i<G.vexnum;i++)
   for(j=0;j<G.vexnum;j++)
    G.arcs[i][j].adj=0;
   for(k=0;k<G.arcnum;k++)
   {
    printf("The %d arc:",k+1);
    scanf(" %c %c",&v1,&v2);
    i=LocateVex(G,v1);//确定v1和v2在G中位置
    j=LocateVex(G,v2);
    G.arcs[i][j].adj=1;
   }
   return true;
}

bool CreateDN(MGraph &G)
{
int i,j,k,w;
VertexType v1,v2;
scanf("%d %d",&G.vexnum,&G.arcnum);
for(i=0; i<G.vexnum; i++)
   scanf(" %c",&G.vexs[i]);
for(i=0;i<G.vexnum;i++)
   for(j=0;j<G.vexnum;j++)
    G.arcs[i][j].adj=INFINITY;
   for(k=0;k<G.arcnum;k++)
   {
    scanf(" %c %c %d",&v1,&v2,&w);
    i=LocateVex(G,v1);//确定v1和v2在G中位置
    j=LocateVex(G,v2);
    G.arcs[i][j].adj=w;
   }
   return true;
}

bool CreateUDN(MGraph &G)
{
int i,j,k,w;
VertexType v1,v2;
scanf("%d %d",&G.vexnum,&G.arcnum);
for(i=0; i<G.vexnum; i++)
   scanf(" %c",&G.vexs[i]);
for(i=0;i<G.vexnum;i++)
   for(j=0;j<G.vexnum;j++)
    G.arcs[i][j].adj=INFINITY;
   for(k=0;k<G.arcnum;k++)
   {
    scanf(" %c %c %d",&v1,&v2,&w);
    i=LocateVex(G,v1);//确定v1和v2在G中位置
    j=LocateVex(G,v2);
    G.arcs[i][j].adj=w;
    G.arcs[j][i]=G.arcs[i][j];
   }
   return true;
}

bool CreateUDG(MGraph &G)
{
int i,j,k;
VertexType v1,v2;
scanf("%d %d",&G.vexnum,&G.arcnum);
for(i=0; i<G.vexnum; i++)
   scanf(" %c",&G.vexs[i]);
for(i=0;i<G.vexnum;i++)
   for(j=0;j<G.vexnum;j++)
    G.arcs[i][j].adj=0;
   for(k=0;k<G.arcnum;k++)
   {
    scanf(" %c %c",&v1,&v2);
    i=LocateVex(G,v1);//确定v1和v2在G中位置
    j=LocateVex(G,v2);
    G.arcs[i][j].adj=1;
    G.arcs[j][i]=G.arcs[i][j];
   }
   return true;
}

bool CreateGraph(MGraph &G)
{
printf("Please input the kind of Graph<DG,DN,UDG,UDN>:");
scanf("%d",&G.kind);
switch(G.kind)
{
   case DG:
    return CreateDG(G);//构造有向图
   case DN:
    return CreateDN(G);//构造有向网
   case UDG:
    return CreateUDG(G);//构造无向图
   case UDN:
    return CreateUDN(G);
   default:
    return false;
}
return true;
}
构造一个具有n个顶点和e条边的无向图的时间复杂图是O(n*n+e*n),其中对G.arcs的初始化耗费了O(n*n)的时间。？？