怎么存一个图是由设计者自己想出来的。
举两个例子而已，真正的如何存一个图，是根据实际问题来决定的。
图有两个要素：
- 顶点
- 边
邻接矩阵
- 顶点
使用数组存顶点 - 边
使用矩阵存储，如果两点之间存在连接关系，那么就设值为1，否则为0：
v0 v1 v2 v3
v0 0 1 1 1
v1 1 0 1 0
v2 1 1 0 1
v3 1 0 1 0
tips：
对于无向图，矩阵是对称的。（i,j 存在连接，则v[i][j]=v[j][i]=1）
#无向图
对于 无向图 来说：节省一半的空间的方法
只存：
v1 1
v2 1 1
v3 1 0 1
使用一维数组
length = 0+1+..+(n-1) = n(n-1)/2
比如上面的矩阵可以只存：
Array= [G10,G20,G21,G30,G31,G32];
所以，Gi,j （i!=j）的位置就是
Array[1+2+3+...+(i-1)+j]
= Array[i(i-1)/2 +j]
#邻接矩阵好处
虽然上述的方式确实可以减少空间的使用，但是也带来了一定的不方便。
邻接矩阵有自己的好处：
* 检查两个点之间是否存在连接。
* 对于某个点的所有邻接点，可以很快全部找到。
* 入度和出度好找。（对于有向的，出度找行，入度找列）
#坏处
存稀疏图的时候
矩阵中有大量的0元素，浪费空间。（对稠密图的话就划算了）
计算有多少相邻的时候，要遍历整个矩阵，浪费时间。
#有权图
把矩阵中的数值设置为相应的权。
邻接表
- 顶点
使用数组 - 边
使用邻接表
有一个数组存着开头指针。
邻接表存储
tips:
我们可以发现，每个头指针，连着 “存储着与相应节点相连的所有节点的链表”
这样每条边被存了两次。
若i,j相连，
则 G[i]指向的链表中存有j
同样 G[j]指向的链表中存有i
=> 若有E条边，则链表的节点共有2E个。
算下存储空间
一个指针占用空间为1，一个节点值占用空间为1
设有N个节点，E条边
那么存储是：
共有N个指针 + 2E×（节点值，指针）
= N + 2E ×2
而原本矩阵的存储方案，占用空间为N*N
所以当 N+4E < N*N
=> E <N(N-1)/4 的时候，使用链表存空间上会划算。
tips:
如果考虑到存权值的话，那就空间要更进一步了...
#好处
* 找到任一顶点的相连的点
*对于稀疏图来说，节省空间
*
对于无向图来说：任一顶点的出入度
对于有向图来说：任一顶点的出度
#坏处
知道两个点之间是否存在连接麻烦
对于有向图：可以左边存出去的，右边存进的。看自己啦。
Paste_Image.png
code
/* 图的邻接矩阵表示法（C语言实现） */
#define MaxVertexNum 100 /* 最大顶点数设为100 */
#define INFINITY 65535 /* ∞设为双字节无符号整数的最大值65535*/
typedef char VertexType; /* 顶点类型设为字符型 */
typedef int EdgeType; /* 边的权值设为整型 */
enum GraphType { DG, UG, DN, UN };
/* 有向图,无向图,有向网图,无向网图*/
typedef struct {
VertexType Vertices[ MaxVertexNum ]; /* 顶点表 */
EdgeType Edges[ MaxVertexNum ][ MaxVertexNum ];
/* 邻接矩阵，即边表 */
int n, e; /* 顶点数n和边数e */
enum GraphType GType; /* 图的类型分4种：UG、DG、UN、DN */
} MGraph; /* MGragh是以邻接矩阵存储的图类型 */
void CreateMGraph ( MGraph *G )
{
int i, j, k, w;
G-> GType = UN; /* Undirected Network 无向网图 */
printf( "请输入顶点数和边数(输入格式为:顶点数, 边数):\n" );
scanf( "%d, %d",&(G->n), &(G->e) ); /* 输入顶点数和边数 */
printf("请输入顶点信息(输入格式为:顶点号<CR>):\n");
for ( i = 0; i < G->n; i++ )
scanf( "%c",&(G-> Vertices[i]) ); /* 输入顶点信息，建立顶点表 */
for ( i = 0; i < G->n; i++ )
for ( j = 0; j < G->n; j++ )
G->Edges[i][j] = INFINITY; /* 初始化邻接矩阵 */
printf( "请输入每条边对应的两个顶点的序号和权值，输入格式为:i, j, w:\n" );
for ( k = 0; k < G->e; k++ ) {
scanf("%d,%d,%d ",&i, &j, &w); /* 输入e条边上的权，建立邻接矩阵 */
G->Edges[i][j] = w;
G->Edges[j][i] = w; /* 因为无向网图的邻接矩阵是对称的 */
}
}
/* 图的邻接表表示法（C语言实现） */
#define MaxVertexNum 100 /* 最大顶点数为100 */
enum GraphType { DG, UG, DN, UN };
/* 有向图,无向图,有向网图,无向网图*/
typedef struct node{ /* 边表结点 */
int AdjV; /* 邻接点域 */
struct node *Next; /* 指向下一个邻接点的指针域 */
/* 若要表示边上的权值信息，则应增加一个数据域Weight */
} EdgeNode;
typedef char VertexType; /* 顶点用字符表示 */
typedef struct Vnode{ /* 顶点表结点 */
VertexType Vertex; /* 顶点域 */
EdgeNode *FirstEdge; /* 边表头指针 */
} VertexNode;
typedef VertexNode AdjList[ MaxVertexNum ]; /* AdjList是邻接表类型 */
typedef struct{
AdjList adjlist; /* 邻接表 */
int n, e; /* 顶点数和边数 */
enum GraphType GType; /* 图的类型分4种：UG、DG、UN、DN */
} ALGraph; /*ALGraph是以邻接表方式存储的图类型 */
void CreateALGraph( ALGraph *G )
{
int i, j, k;
EdgeNode *edge;
G-> GType = DG; /* Directed Graph 有向图 */
printf( "请输入顶点数和边数(输入格式为:顶点数,边数)：\n" );
scanf( "%d,%d", &(G->n), &(G->e) ); /* 读入顶点数和边数 */
printf( "请输入顶点信息(输入格式为:顶点号<CR>)：\n" );
for ( i=0; i < G->n; i++ ) { /* 建立有n个顶点的顶点表 */
scanf( " %c", &(G->adjlist[i].Vertex) ); /* 读入顶点信息 */
G->adjlist[i].FirstEdge = NULL; /* 顶点的边表头指针设为空 */
}
printf( "请输入边的信息(输入格式为: i, j <CR>)：\n" );
for ( k=0; k < G->e; k++ ){ /* 建立边表 */
scanf( "\n%d,%d", &i, &j); /* 读入边<vi,vj>的顶点对应序号*/
edge = (EdgeNode*)malloc(sizeof(EdgeNode)); /* 生成新边结点edge */
edge->AdjV = j; /* 邻接点序号为j */
edge->Next = G->adjlist[i].FirstEdge;
/* 将新边表结点edge插入到顶点vi的边表头部 */
G->adjlist[i].FirstEdge = edge;
/* 若是无向图，还要生成一个结点，用来表示边< vj, vi> */
}
}
