图的存储结构：邻接矩阵和邻接表

 图         graph

顶点        vertex

弧        arc

弧尾        tail

弧头        head

有向图        digraph

边        edge

无向图        undigraph

权        weight

网        network

邻接点        adjacent

依附        incident

度        degree

出度        OutDegree

入度        Indegree

路径        path

邻接矩阵        adjacency matrix 

一、邻接矩阵存储（数组表示）

借助矩阵（二维数组）表示元素（图的任意两个顶点）之间的关系

用一维数组（顶点表）存储顶点，二维数组（邻接矩阵）存储顶点间的关系；

 图（有向图），无向图为对称矩阵

 网：矩阵元素为权值，其余∞

图的邻接矩阵存储结构

#define VerNum 100
#define MaxInt 32767
typedef char VertexType;
typedef int ArcType;
typedef struct{
    VertexType ver[VerNum];//顶点表；一维数组存储顶点
    ArcType arc[VerNum][VerNum];//邻接矩阵；二维数组存贮顶点间关系；
    int vernum,arcnum;//图的当前顶点数和边数；
}AMGraph;

 无向网的创建

Status CreateUDN(AMGraph &G){
    scanf("%d %d",G.vernum,G.arcnum);//
    for(int i=0;i<vernum;++i){
        scanf("%c",&G.ver[i]);
    }                                /（顶点值）输入顶点表
    for(int i=0;i<vernum;++i){
        for(int j=0;j<vernum;++j){
            G.arc[i][j]=MaxInt;
        }
    }//初始化邻接矩阵
    
    for(k=0;k<G.arcnum;++k){
        scanf("%d %d %d",&v1,&v2,&w);
        i=LocVex(G,v1);
        j=LocVex(G,v2);//确定顶点在定点表的坐标
        G.arc[i][j]=w;//将对应权值置为w
        G.arc[j][i]=w;
    }                                /（权值）输入邻接矩阵
    return OK;
}

 不足：

不方便增加、删减顶点

浪费存储空间；

二、邻接表存储（链式）

无向图（有向图则只有出度）

 邻接表的创建：

typedef struct ArcNode{
    int adjvex;
    struct ArcNode* nextarc;//指向下一条边的指针；
    OtherInfo info;
}ArcNode;

typedef struct VNode{
    VertexType data;
    ArcNode* firstarc;
}VNode，AdjList[MaxInt];//邻接表；
typedef struct{
    AdjList vertices;
    int vexnum,arcnum;
}ALGraph;

Status CreateUDG(ALGraph &G){
    scanf("%d %d",G.vexnum,G.arcnum);//输入顶点数和总边数；
    for(i=0;i<vexnum;++i){
        scanf("%c",G.vertices[i].data);
        G.vertices[i].firstarc=NULL;
    }//输入顶点表；
    for(k=0;k<G.arcnum;++k){
        scanf("%d %d",&v1,&v2);//输入边的两个顶点
        i=LocVex(G,v1);j=LocVex(G,v2);
        
        p1=new ArcNode;
        p1->adjvex=j;//邻接点序号为j
        p1->nextarc=G.vertices[i].firstarc;
        G.vertices[i].firstarc=p1;
        //头插法插入表结点，其中i为表头，j为插入的邻接点
        
        p2=new ArcNode;
        p2->adjvex=i;
        p2->nextarc=G.vertices[j].firstarc;
        G.vertices[j].firstarc=p2;
        //头插法插入对称的表结点；即j为表头，i为邻接点；
    }
    return OK;
}

 邻接矩阵和邻接表的关系