图的存储结构

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

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

   图有以下几种存储结构

 

 

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;//图的种类标示

}my_graph;

    有时候为了方便确定顶点入度或以顶点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;

 

typedef struct{

    vexbox adjmulist[max_vertex_num];

    int vexnum,edgenum;//无向图的顶点数和边数

}AMLGraph;