Contents

• 常用的就是邻接矩阵，邻接表，链式前向星

#include <cstdio>
//图的储存结构

#define MAXVEX 100                      //最大顶点数,应由用户定义
#define INFINITY 65535                  //用65535来代表∞

//邻接矩阵表示法   有向图,无向图的表示法 ， 无向图是对称的
typedef char VertexType;                //顶点类型应用户定义
typedef int  EdgeType;                  //边上的权值应由用户定义
typedef int InforType;                  //信息的类型由用户定义

typedef struct Graph{
    VertexType vexs[MAXVEX];            //顶点表
    EdgeType arc[MAXVEX][MAXVEX];       //邻接矩阵,
    int numVertexes, numEdge;           //图中当前的顶点数和边数
}Graph;




//邻接表表示法  无向图的表示法
typedef struct EdgeNode                //边表结点
{
    int adjvex;                        //邻接点域,存储该顶点对应的下标
    EdgeType weight;                   //用于存储权值,对于非网图可以不需要
    struct EdgeNode *next;             //链域,指向下一个邻接点
}EdgeNode;

typedef struct VertexNode              //顶点表结点
{
    VertexType data;                   //顶点域,存储顶点信息
    EdgeNode *firstdege;               //边表头指针  建立边表
}VertexNode;

typedef struct GraphAdjlist
{
    VertexNode adjlist[MAXVEX];        //建立顶点表
    int numVertex, numEdge;            //图中当前顶点数和边数
}GraphAdjlist;



//十字链表表示法  有向图的优化存储结构
typedef struct ArcNode{                //边表结点
    int tailvex, headvex;              //该弧的尾和头顶点的位置
    struct AcrNode *hlink, *tlink;     //分别为弧头相同和弧尾相同的链域
    InforType *infor;                      //该弧相关信息的指针
}ArcNode;

typedef struct VexNode{                 //顶点结点
    VertexType data;
    ArcNode *firstin, *firstout;        //分别指向该顶点第一条入弧和出弧
}VexNode;

typedef struct OLGraph{
    VexNode xlist[MAXVEX];              //顶点表
    int numVertex, numEdge;             //有向图的当前顶点和弧数
}OLGraph;


//多重链表表示法  无向图的优化存储结构
typedef struct Edgenode{                //边表结点
    int ivex, jvex;                     //该边依附的两个顶点的下标
    int mark;
    struct Arcnode *ilink, *jlink;      //分别指向依附这两个顶点的下一条边
    InforType *infor;                   //该边的信息指针
}Edgenode;

typedef struct Vexnode{
    VertexType data;
    Edgenode *firstedge;                //指向第一条依附该顶点的边
}Vexnode;

typedef struct AMLGraph{
    Vexnode adjlist[MAXVEX];
    int numvex, numedge;                //无向图的当前顶点数和边数
}AMLGraph;