图的存储结构

　　图的结构比较复杂，任意两个顶点之间都可能有联系，因此无法以数据元素在存储区中的物理位置来确定元素的关系，所以图没有顺序映像的存储结构，但是可以借助数组的数据类型来表示元素之间的关系。

　　另一方面，用多重链表表示图是自然的事，他是×××一种最简单的链式映像存储结构，即由一个数据域和多个指针域组成的节点表示图中的一个顶点，其中数据域存放顶点的信息，指针域指向其邻接点的指针。

　　图有以下几种存储结构

　　1 数组（邻接矩阵）表示法

　　用两个数组分表存储图的顶点信息和数据元素之间的关系（也就是图的边或弧的信息）

　　形式如下：

　　--------------图的数组（邻接矩阵）存储表示-----------

　　#define INFINITY int_max;//最大值（无穷大表示两点之间没关系）

　　#define MAX_VERTEX_NUM 20;//最大的顶点数

　　typedef enum GraphKind{dg,udg,dn,udn};//图的类别：有向图，无向图，有向网，无向网

　　typedef struct ArcCell{//矩阵元素

　　int ac_val;//顶点的关系类型，对无权图，用1或0表示是否相邻，如果是有权图，表示为权值

　　char *ac_info;//该弧表示的信息

　　}adj_matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

　　typedef struct Graph{

　　struct VNode *g_vetxs;//顶点信息的数组

　　struct ArcCell **g_mat;//邻接矩阵，也就是弧（边）的信息二维数组

　　int  g_vexnum; //图的顶点数

　　int  g_arcnum;//图的弧数

　　emu GraphKind g_kind;//图的类型

　　}my_graph;

　　从结构上讲就是用一个二维数组（邻接矩阵）来存储图的弧（边）的信息，用一个一维数组存储图的顶点信息。

　　1   2  3

　　1【0，1，1】

　　2【0，0，0】

　　3【1，0，0】

　　如果是无权图，邻接矩阵里面只存储0或1的数据，来表示两个顶点之间是否有联系。比如上图矩阵，从下标1开始描述顶点数组，图中表示第一个顶点和第二个顶点有联系，第一个顶点和第三个顶点有联系，第三个和第一个有联系。第2个和第一个没联系（那是因为有可能图是有向图，从顶点1到2有箭头联系，从顶点2到1却没有箭头）。所以如果图是无向图的话，可以只存储矩阵上三角或者下三角元素，因为在无向图中从顶点1和顶点2之间有联系，但是没有箭头指向。

　　如果是有权图，则上面矩阵中1应该变成从顶点1到顶点2之间这个弧的具体权值，而不是单纯的1.如果之间没有边，没有联系，那就要用一个特殊的符号（比如#，∞）来表示这个两个顶点之间没有边或弧。（但是不能用0，因为0也是一个数值，也可以是弧的权值数值）

　　2 邻接表

　　邻接表是图的一种链式存储结构。在邻接表中对图中的每个顶点建立一个单链表（比如图有4个顶点，就要建立4个单链表），第i个单链表依附于图的第i个顶点（如果是有向图就是以顶点i为弧尾的边）。

　　-----------------存储代码---------------

　　#define MAX_VERTEX_NUM 20 //最大顶点数

　　typedef enum GraphKined{dg,udg,dn,udn};//图的类别：有向图，无向图，有向网，无向网

　　typedef struct ArcNode {//边节点

　　int an_index;//边节点编号

　　char *an_info;//边节点信息

　　struct ArcNode *nextarc;//指向下一边节点

　　};

　　type struct VetxNode{//顶点节点

　　int vn_data;//顶点编号

　　struct ArcNode *vn_firstarc;//指向顶点第一条指出边

　　}vtex_list[MAX_VERTEX_NUM];

　　typedef struct Graph{//描绘整个图的结构

　　struct VetxNode *g_vetxlist;//指向顶点数组

　　int g_vexnum; //图的顶点数

　　int g_arcnum;//图的弧数

　　enum GraphKind g_kind;//图的种类标示

　　有时候为了方便确定顶点入度或以顶点i为头的弧（针对有向图来说），则需要建立以顶点i为头的弧的链表。这称为逆邻接表，邻接表和逆邻接表可以方便的查询图中一个顶点的入度和出度

　　3 十字链表

　　在十字链表中（有向图适用，有向图才有弧头和弧尾的概念），每条弧有一个结点，每个顶点也有个结点。

　　-------------存储结构和结点的结构说明---------

　　#define MAX_VERTEX_NUM 20;

　　typedef struct ArcNode{//弧结点

　　int an_tailvetx;//该弧的尾点在图中的位置

　　int an_headvetx;//该弧的头顶点在图中的位置

　　struct ArcNode *hlink,&tlink;//分别是弧头相同，弧尾相同的弧的指针

　　InfoType *info;//该弧的信息

　　}

　　typedef struct VexNode{//顶点结点

　　vertexType data;//顶点数据

　　ArcBox *firstIn,*firstOut;//分别指向该顶点的第一个入弧和出弧

　　}vexBode;

　　typedef struct{

　　vexnode xlist[max_vertex_num];//表头变量，顶点数组

　　int vexnum,arcnum;//顶点数量，弧数量

　　}OlGraph//图整体概念结构

　　4.邻接多重表

　　这个结构是无向图的链式存储结构。和十字链表很相似，但是添加一个是否访问过的标示。

　　---------------存储结构------------

　　#define max_vertex_num 20

　　type enum{unvisited,visited }visitIf;

　　typedef struct EBox{

　　visitIf mark;//访问标示

　　int ivex,jvex;//该边依附的两个顶点的位置。

　　struct EBox *ilink,*jlink;//ilink表示依附顶点ivex的边，jlink表示依附顶点jvex的边

　　Infotype *info;//边信息

　　}EBox;

　　typedef struct vexBox{

　　verterType data;

　　EBox *firstedge;//指向第一条依附该顶点的边

　　}VexBox;