图的基本概念|存储-图的存储及基本操作

邻接矩阵法

所谓邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中
边的信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵。
顶点数为n的图G=(V,E)的邻接矩阵A是$n\times n$的，将G的顶点编号为$v_1,v_2,\dots ,v_n$，则
$$A[i][j]=\{\begin{array}{c}1,(v_i,v_j)或<v_i,v_j>是E(G)中的边\\ 0,(v_i,v_j)或<v_i,v_j>不是E(G)中的边\end{array}$$
对带权图而言，若顶点v和v之间有边相连，则邻接矩阵中对应项存放着该边对应的权值，若顶点$v_i$和$v_j$不相连，则通常用0或$\infty$来代表这两个顶点之间不存在边：
KaTeX parse error: Can't use function '$' in math mode at position 32: …\begin{matrix} $̲w_{ij}$,\qquad …

邻接矩阵存储结构定义

#define MaxVertexNum 100                        // 顶点数目的最大值
typedef char VertexType;                        // 顶点对应的数据类型
typedef int EdgeType;                           // 边对应的数据类型
typedef struct
{
	VertexType vex[MaxVertexNum];               // 顶点表
	EdgeType edge[MaxVertexNum][MaxVertexNum];  // 邻接矩阵，边表
	int vexnum, arcnum;                         // 图的当前顶点数和边数
}MGraph;

图的邻接矩阵存储表示法具有以下特点：

1. 无向图的邻接矩阵一定是一个对称矩阵（并且唯一)。因此，在实际存储邻接矩阵时只需
   存储上（或下）三角矩阵的元素。
2. 对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非元素）的个数正好是顶点i的度TD($v_i$)。
3. 对于有向图，邻接矩阵的第i行非零元素（或非$\infty$元素）的个数正好是顶点i的出度 OD($v_i$)；第i列非零元素（或非$\infty$元素）的个数正好是顶点i的入度ID($v_i$)。
4. 用邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图
   中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。
5. 稠密图（即边数较多的图）适合采用邻接矩阵的存储表示。
6. 设图G的邻接矩阵为A，$A^n$的元素$A^n[i][j]$等于由顶点i到顶点j的长度为n的路径的数目。

邻接表法

当一个图为稀疏图时，使用邻接矩阵法显然会浪费大量的存储空间，而图的邻接表法结合了顺序存储和链式存储方法，大大减少了这种不必要的浪费。
所谓邻接表，是指对图G中的每个顶点$v_i$建立一个单链表，第i个单链表中的结点表示依附于顶点$v_i$的边（对于有向图则是以顶点$v_i$为尾的弧），这个单链表就称为顶点$v_i$的边表（对于有向图则称为出边表）。边表的头指针和顶点的数据信息采用顺序存储，称为顶点表，所以在邻接表中存在两种结点：顶点表结点和边表结点

顶点表结点由两个域组成：顶点域（data）存储顶点$v_i$的相关信息，边表头指针域（firstarc）指向第一条边的边表结点。
边表结点至少由两个域组成：邻接点域（adjvex）存储与头结点顶点$v_i$邻接的顶点编号，指针域（nextarc）指向下一条边的边表结点。

邻接表存储结构定义

#define MaxVertexNum 100         // 图中顶点数目的最大值
typedef char VertexType;         // 顶点类型
typedef int EdgeType;            // 边的权值的类型
// 边/弧
typedef struct ArcNode           // 边表节点
{
	int adjvex;                  // 该弧所指向的顶点的位置
	struct ArcNode* nextarc;     // 指向下一条弧的指针
	// InfoType info;            // 网的边权值
}ArcNode;
// 顶点
typedef struct VNode             // 顶点表节点
{
	VertexType data;             // 顶点信息
	ArcNode* firstarc;           // 指向第一条依附该顶点的弧的指针
}VNode, AdjList[MaxVertexNum];
// 用邻接表存储的图
typedef struct
{
	AdjList vertices;            // 邻接表
	int vexnum, arcnum;          // 图的顶点数和弧数
}ALGraph;                        // ALGraph是以邻接表存储的图类型

1. 若G为无向图，则所需的存储空间为$O(|V|+2|E|)$：若G为有向图，则所需的存储空间为 $O(|V|+|E|）$。前者的倍数2是因为在无向图中，每条边在邻接表中出现了两次。
2. 对于稀疏图（即边数较少的图），采用邻接表表示将极大地节省存储空间。
3. 在邻接表中，给定一个顶点，能很容易地找出它的所有邻边，因为只需要读取它的邻接表。在邻接矩阵中，相同的操作则需要扫描一行，花费的时间为O(n)。但是，若要确定给定的两个顶点间是否存在边，则在邻接矩阵中可以立刻查到，而在邻接表中则需要在相应结点对应的边表中查找另一结点，效率较低。
4. 在无向图的邻接表中，求某个顶点的度只需计算其邻接表中的边表结点个数。在有向图的邻接表中，求某个顶点的出度只需计算其邻接表中的边表结点个数；但求某个顶点x的入度则需遍历全部的邻接表，统计邻接点（adjvex）域为x的边表结点个数。
5. 图的邻接表表示并不唯一，因为在每个顶点对应的边表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。