图的存储结构

1）数组表示法

//-----图的组（邻接矩阵）存储表示-----
#define INFINITY INT_MAX //最大值∞
#define MAX_VERTEX_NUM 20 //最大的顶点个数
typedef enum {DG,DN,UDG,UDN}GraphKind; //{有向图（Digraph），有向网（DiNet），无向图(UniDigraph),无向网} 
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; //图的种类标志
}MGpraph

2）邻接表

//---------图的邻接表存储表示-----------
#define MAX_VERTEX_NUM 20
typedef struct ArcNode{
    int adjvex; //该弧指向的顶点的位置
    struct ArcNode *nextarc; //指向下一条弧的指针
    InfoType *info; //该弧相关信息的指针
}ArcNode;
typedef struct VNode{
    VertexType data; //顶点信息
    ArcNode *firstarc;  //指向的一条依附该顶点的弧的指针
}VNode，AdjList[MAX_VERTEX_NUM]；
typedef struct{
    AdjList vertices;
    int vexnum,arcnum; //图的当前顶点数和弧数
    int kind; //图的种类
}

3）十字链表法

十字路口有方向，十字链表法是专门针对有向图设计的，旨在解决有向图用邻接表法找不到入度的这个问题。顶点结点包含三个域，数据域，firstin和firstout域分别指向第一个入度边，第一个出度边；边结点有五个域，尾域头域分别表示该弧的弧尾和弧头，链域tlink指向弧尾相同的下一条弧，hlink指向弧头相同的下一条弧，这样弧头相同的弧就在一个链表上，弧尾相同的弧也在一个链表上，info域指向该弧的相关信息。