1. 定义
之前在线性表中，我们可以看到，数据元素之间是被串起来的，仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关。现实情况下，人与人之间的关系就不仅仅是这样的，就不是简单的一对一或者一对多，而是多对多的情况。
图是由顶点的有穷非空集合和顶点之间边的集合组成。通常表示为：G(V,E)。其中G表示一个图，V是图G中的顶点集合，E是图G中边的集合
2. 图的存储
那么如何存储图呢？
由定义我们可以知道，图是由两部分组成，顶点和边，顶点和边的连接，确定了图的逻辑关系，所以图的存储，其中它的顶点需要存储，边与边的连接信息也要存储。
3.邻接矩阵
顶点的信息，可以使用一维数组进行存储
边的信息，存在这多对多的逻辑关系，那么可以使用二维数据进行存储
邻接矩阵的存储，其实就是顺序存储的方式
图上的度指的是：存在关系的顶点数
邻接矩阵存储实现思路
1、 确定顶点数
2、 读取顶点信息
3、 初始化邻接矩阵
4、 读入边的信息
5、 循环打印
邻接矩阵存储图的数据结构
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXVEX 100 /* 最大顶点数，应由用户定义 */
#define INFINITYC 0
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */
typedef struct
{
VertexType vexs[MAXVEX]; /* 顶点表 */
EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */
int numNodes, numEdges; /* 图中当前的顶点数和边数 */
}MGraph;
存储部分
void CreateMGraph(MGraph *G){
int i,j,k,w;
printf("输入顶点数和边数\n");
scanf("%d,%d",&G->numNodes,&G->numEdges);
printf("顶点数：%d,边数：%d\n",G->numNodes,G->numEdges);
// 输入顶点信息，组成顶点表
for (i = 0; i<=G->numNodes; i++) {
scanf("%c",&G->vexs[i]);
}
// 初始化邻接矩阵
for (i = 0; i<=G->numNodes; i++) {
for (j = 0; j<=G->numNodes; j++) {
G->arc[i][j] = INFINITYC; // 初始化0
}
}
// 输入边表数据
for (k = 0; k<G->numEdges; k++) {
printf("输入边（vi,vj）上的下标i，下标j，权w\n");
scanf("%d,%d,%d",&i,&j,&w);
G->arc[i][j] = w;
//如果是无向图的话 矩阵对阵
G->arc[j][i] = w;
}
// 打印邻接矩阵
printf("矩阵结果\n");
for (int i = 0; i < G->numNodes; i++) {
printf("\n");
for (int j = 0; j < G->numNodes; j++) {
printf("%d ",G->arc[i][j]);
}
}
printf("\n");
}
/**
输入顶点数和边数
4,5
顶点数：4,边数：5
abcd
输入边（vi,vj）上的下标i，下标j，权w
0,1,1
输入边（vi,vj）上的下标i，下标j，权w
0,2,1
输入边（vi,vj）上的下标i，下标j，权w
0,3,1
输入边（vi,vj）上的下标i，下标j，权w
1,2,1
输入边（vi,vj）上的下标i，下标j，权w
2,3,1
矩阵结果
0 1 1 1
1 0 1 0
1 1 0 1
1 0 1 0
*/
4. 邻接表
同样的，邻接矩阵（顺序存储）的方式，可能会产生一些空白的空间，会造成空间的浪费，那么，我们尝试使用链式的存储。
邻接表中首先有一个一维数组（如图中绿色部分），上图绿色的部分存储的是图的顶点信息，在这个一维数组中的某一个顶点数据，指向了一个链表。一维数组中的数据，类似链表中的表头。链表中的数据都是与其有着顶点的连接逻辑关系的。
假如边有权重，那么邻接表的节点可以添加一个权重。
邻接表存储的数据结构设计
#define M 100
#define true 1
#define false 0
typedef char Element;
typedef int BOOL;
//邻接表的节点
typedef struct Node{
int adj_vex_index; //弧头的下标，也就是被指向的下标
Element data; //权重值
struct Node * next; //边指针
}EdgeNode;
//顶点节点表
typedef struct vNode{
Element data; //顶点的权值
EdgeNode * firstedge; //顶点下一个是谁？
}VertexNode, Adjlist[M];
//总图的一些信息
typedef struct Graph{
Adjlist adjlist; //顶点表
int arc_num; //边的个数
int node_num; //节点个数
BOOL is_directed; //是不是有向图
}Graph, *GraphLink;
存储部分
void creatGraph(GraphLink *g){
int i,j,k;
EdgeNode *p;
//1. 顶点,边,是否有向
printf("输入顶点数目,边数和有向？：\n");
scanf("%d %d %d", &(*g)->node_num, &(*g)->arc_num, &(*g)->is_directed);
//2.顶点表
printf("输入顶点信息：\n");
for (i = 0; i < (*g)->node_num; i++) {
getchar();
scanf("%c", &(*g)->adjlist[i].data);
(*g)->adjlist[i].firstedge = NULL;
}
//3.录入数据
printf("输入边信息：\n");
for (k = 0; k < (*g)->arc_num; k++){
getchar();
scanf("%d %d", &i, &j);
//①新建一个节点
p = (EdgeNode *)malloc(sizeof(EdgeNode));
//②弧头的下标
p->adj_vex_index = j;
//③头插法插进去，插的时候要找到弧尾，那就是顶点数组的下标i
p->next = (*g)->adjlist[i].firstedge;
//④将顶点数组[i].firstedge 设置为p
(*g)->adjlist[i].firstedge = p;
//j->i
if(!(*g)->is_directed)
{
// j -----> i
//①新建一个节点
p = (EdgeNode *)malloc(sizeof(EdgeNode));
//②弧头的下标i
p->adj_vex_index = i;
//③头插法插进去，插的时候要找到弧尾，那就是顶点数组的下标i
p->next = (*g)->adjlist[j].firstedge;
//④将顶点数组[i].firstedge 设置为p
(*g)->adjlist[j].firstedge = p;
}
}
}