图的储存

最基本的图论。。。但是也不能松懈啊

有邻接矩阵，邻接链表。。。

1.1        无向图的数组表示
(1)   无权图的邻接矩阵
无向无权图G=(V，E)有n(n≧1)个顶点，其邻接矩阵是n阶对称方阵。其元素的定义如下：

(2)   带权图的邻接矩阵
无向带权图G=(V，E)的邻接矩阵元素的定义如下：

(3)   无向图邻接矩阵的特性
a)        邻接矩阵是对称方阵；
b)        对于顶点vi，其度数是第i行(或第i列)的非0元素的个数；
c)        无向图的边数是上(或下)三角形矩阵中非0元素个数。
1.2        有向图的数组表示

(1)   无权图的邻接矩阵

若有向无权图G=(V，E)有n(n≧1)个顶点，其邻接矩阵元素定义如下：

(2)   带权图的邻接矩阵

有向带权图G=(V，E)的邻接矩阵元素的定义如下：

(3)   有向图邻接矩阵的特性

1. a) 对于顶点v_i，第i行的非0元素的个数是其出度OD(v_i)；第i列的非0元素的个数是其入度ID(v_i)。
2. b) 邻接矩阵中非0元素的个数就是图的弧的数目。

2  邻接表
基本思想：对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。每一个单链表设一个表头结点。第i个单链表表示依附于顶点Vi的边(对有向图是以顶点Vi为头或尾的弧)。

2.1链表中的结点称为表结点，每个结点由三个域组成，如图所示。其中邻接点域(adjvex)指示与顶点Vi邻接的顶点在图中的位置(顶点编号)，链域(nextarc)指向下一个与顶点Vi邻接的表结点，数据域(info)存储和边或弧相关的信息，如权值等。对于无权图，如果没有与边相关的其他信息，可省略此域。
每个链表设一个表头结点(称为顶点结点)，由两个域组成，如图所示。链域(firstarc)指向链表中的第一个结点，数据域(data)存储顶点名或其他信息。

在图的邻接表中，所有顶点结点用一个向量以顺序结构形式存储，可以随机访问任意顶点的链表，该向量称为表头向量，向量的下标指示顶点的序号。

//图的邻接表存储表示
#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;                   //图的种类标志
}ALGraph;

2.2 示例
用邻接表存储图时，对无向图，其邻接表是唯一的，对有向图，其邻接表有两种形式，如图所示。

3数组模拟链表

struct node
{
	int u,w,v,next;
}e[200010];
int st[MAXN];
void add(int x,int y,int z)
{
    e[++tot].u=x;
    e[tot].v=y;
    e[tot].w=z;
    e[tot].next=st[x];
    st[x]=tot;
}