//create graph
#include<iostream>
#include<iomanip>//打印邻接矩阵时提供setw函数来置表位
#define MAX 20//图的顶点个数最大值，也可以不设置这个，用堆分配
using namespace std;

typedef enum{DG,UDG,DN,UDN}GraphKind;

typedef struct{
    int adj;
    //InfoType *info
}ArcNode,AdjMatrix[MAX][MAX];

typedef struct{
    int vexnum,arcnum;
    AdjMatrix arcs;
    int vertex[MAX];//假设顶点值为int类型
    GraphKind kind;
}MGraph;
//返回顶点位置
int Locate(const MGraph &G,int vex){
    for(int i=0;i<G.vexnum;++i){
        if(G.vertex[i]==vex)
            return i;
    }
    return INT_MAX;
}
//构造有向图
bool createDG(MGraph &G){
    cout<<"\nInput "<<G.vexnum<<" Vertices : ";
    for(int i=0;i<G.vexnum;++i)
        cin>>G.vertex[i];
    for(int i=0;i<G.vexnum;++i)
        for(int j=0;j<G.vexnum;++j)
            G.arcs[i][j].adj=0;
    cout<<"Input "<<G.arcnum<<" Arcs : "<<endl;
    for(int i=0;i<G.arcnum;++i){
        int v1,v2;
        int p=Locate(G,v1);
        int q=Locate(G,v2);
        if(p>=INT_MAX||q>=INT_MAX) return false;
        G.arcs[p][q].adj=1;
    }
    return true;
}
//构造无向图
bool createUDG(MGraph &G){
    cout<<"\nInput "<<G.vexnum<<" Vertices : ";
    for(int i=0;i<G.vexnum;++i)
        cin>>G.vertex[i];
    for(int i=0;i<G.vexnum;++i)
        for(int j=0;j<G.vexnum;++j)
            G.arcs[i][j].adj=0;
    cout<<"Input "<<G.arcnum<<" Arcs : "<<endl;
    for(int i=0;i<G.arcnum;++i){
        int v1,v2;
        cin>>v1>>v2;
        int p=Locate(G,v1);
        int q=Locate(G,v2);
        if(p>=INT_MAX||q>=INT_MAX) return false;
        G.arcs[p][q].adj=1;
        G.arcs[q][p].adj=1;
    }
    return true;
}
//构造有向网
bool createDN(MGraph &G){
    cout<<"\nInput "<<G.vexnum<<" Vertices : ";
    for(int i=0;i<G.vexnum;++i){
        cin>>G.vertex[i];
    }
    for(int i=0;i<G.vexnum;++i){
        for(int j=0;j<G.vexnum;++j){
            G.arcs[i][j].adj=INT_MAX;
        }
    }
    cout<<"Input "<<G.arcnum<<" Arcs : "<<endl;
    for(int i=0;i<G.arcnum;++i){
        int v1,v2,w;
        cin>>v1>>v2>>w;
        int p=Locate(G,v1);
        int q=Locate(G,v2);
        if(p>=INT_MAX||q>=INT_MAX) return false;
        G.arcs[p][q].adj=w;
    }
    return true;
}
//构造无向网
bool createUDN(MGraph &G){
    cout<<"\nInput "<<G.vexnum<<" Vertices : ";
    for(int i=0;i<G.vexnum;++i){
        cin>>G.vertex[i];
    }
    for(int i=0;i<G.vexnum;++i){
        for(int j=0;j<G.vexnum;++j){
            G.arcs[i][j].adj=INT_MAX;
        }
    }
    cout<<"Input "<<G.arcnum<<" Arcs : "<<endl;
    for(int i=0;i<G.arcnum;++i){
        int v1,v2,w;
        cin>>v1>>v2>>w;
        int p=Locate(G,v1);
        int q=Locate(G,v2);
        if(p>=INT_MAX||q>=INT_MAX) return false;
        G.arcs[p][q].adj=w;
        G.arcs[q][p].adj=w;
    }
    return true;
}
//构造图
bool createGraph(MGraph &G){
    switch(G.kind){
        case DG:
            return createDG(G);
        case UDG:
            return createUDG(G);
        case DN:
            return createDN(G);
        case UDN:
            return createUDN(G);
        default:
            return false;
    }
}
//打印邻接矩阵
void displayAdjMatrix(const MGraph &G){
    for(int i=0;i<G.vexnum;++i){
        for(int j=0;j<G.vexnum;++j){
            if(G.arcs[i][j].adj>=INT_MAX)
                cout<<setw(5)<<right<<"  INF";
            else cout<<setw(5)<<right<<G.arcs[i][j].adj;
        }
        cout<<endl;
    }
}
//测试
int main(){
    MGraph graph;
    int kind;
    
    cout<<"Create A Graph in Adjacent Matrix ."<<endl;
    cout<<"1-DG , 2-UDG , 3-DN , 4-UDN"<<endl;
    cout<<"Graph Kind : ";
    cin>>kind;
    if(kind==1)graph.kind=DG;
    else if(kind==2) graph.kind=UDG;
    else if(kind==3) graph.kind=DN;
    else if(kind==4) graph.kind=UDN;
    else{
        cout<<"Invalid Graph Type.";
        return 0;
    }
    cout<<"Vertices Number : ";
    cin>>graph.vexnum;
    cout<<"Arcs Number : ";
    cin>>graph.arcnum;
    
    if (createGraph(graph)){
        cout<<"\nthe Adjacent Matrix is : "<<endl;
        displayAdjMatrix(graph);
    }else cout<<"Invalid input , None Matching Vertex."<<flush;
}

用邻接矩阵的存储方式构造一个图的时间复杂度为O( n^2+e*n)

其中e为弧的数目，初始化邻接矩阵O(n^2)，输入弧需要定位，查找顶点位置O(n)，设置完所有弧需要O(e*n)