图在现实里到处都是，地图导航里的路口和道路，社交网络里的人和关注关系，网页之间的超链接，背后都是图。要在计算机里用图，第一步就是把顶点和边存进内存。图的存法直接决定了后面查找某条边快不快、遍历方不方便，选错了存法，稀疏图会白白占掉一大块内存。

这一节我们讲两种最基础的存法，邻接矩阵和邻接表。先交代图的基本概念，再拿一个具体的小图把两种存法都建出来，最后列一张表对比各自的适用场景。读之前只需要熟悉数组和链表这两种结构。

1. 图的基本概念

图由顶点的有穷非空集合和顶点之间边的集合组成，记作 G = (V, E)，V 是顶点集合，E 是边集合。边分两种。两个顶点之间的边没有方向，叫无向边，写成无序对 (Vi, Vj)。边有方向，从 Vi 指向 Vj，叫有向边，写成有序对 <Vi, Vj>。方向反过来就是另一条边，<Vi, Vj> 和 <Vj, Vi> 是两条不同的有向边。

图里所有边都是无向边，就叫无向图。所有边都是有向边，就叫有向图。如果图里任意两个顶点之间都有边，就叫完全图。含 n 个顶点的无向完全图，边数是 n(n-1)/2，因为每对顶点只算一条。含 n 个顶点的有向完全图，边数是 n(n-1)，因为两个方向各算一条。拿 n=4 代入，无向完全图有 4 乘 3 除以 2 等于 6 条边，有向完全图有 4 乘 3 等于 12 条边。

边还可以带一个和它相关的数，这个数叫权，可能表示距离、耗时、花费。带权的图通常叫网。例如地图导航里每条路权值是里程，找最短路径就是在网上算最小权值和。后面要写的存储代码里，边表里那个 mWeight 字段就是用来放这个权值的。

2. 邻接矩阵

概念清楚了，我们先看邻接矩阵。它用两个数组分别存顶点和边。顶点本身用一个一维数组存，边的关系用一个二维方阵存。两个顶点 i 和 j 之间有边，矩阵里 arc[i][j] 就填权值，没边就填 0 或者一个很大的数表示不存在。

我们拿一个具体的无向图看。4 个顶点 V0 到 V3，边有四条，分别是 V0 连 V1，V0 连 V2，V1 连 V2，V1 连 V3。因为是无向图，矩阵关于主对角线对称，建出来是这样的：

有了这个矩阵，很多信息一眼就能读出来。判断 V1 和 V3 之间有没有边，看 arc[1][3] 是不是 0 就行，一步到位。算 V1 连了几条边，把矩阵第 1 行加起来，1 加 0 加 1 加 1 等于 3，V1 的度就是 3。找 V0 的所有邻接点，把第 0 行扫一遍，arc[0][1] 和 arc[0][2] 是 1，邻接点就是 V1 和 V2。

对应的 C++ 实现如下，构造函数接收顶点数组和边矩阵，先把顶点拷进数组，再开一个 n 乘 n 的二维数组把边矩阵原样复制过来。

template<class VertexType>
class MyGraph {
public:
	template<class MatrixType>
	MyGraph(int numVex, int numEdges, VertexType* vexes, MatrixType edges);
public:
	VertexType* pVertexes; //顶点数组
	int** pEdges; //邻接矩阵，边集
	int mNumVertexes; //顶点数
	int mNumEdges; //边数
};

//初始化邻接矩阵
template<class VertexType> template<class MatrixType>
MyGraph<VertexType>::MyGraph(int numVex, int numEdges, VertexType* vexes, MatrixType edges)
{
	this->mNumEdges = numEdges;
	this->mNumVertexes = numVex;

	//创建并初始化顶点数组
	this->pVertexes = new VertexType[numVex];
	for (int i = 0; i < numVex; ++i) {
		this->pVertexes[i] = vexes[i];
	}
	//创建并初始化邻接矩阵
	this->pEdges = new int* [this->mNumVertexes];
	for (int i = 0; i < this->mNumVertexes; ++i) {
		this->pEdges[i] = new int[this->mNumVertexes];
	}
	for (int i = 0; i < this->mNumVertexes; ++i) {
		for (int j = 0; j < this->mNumVertexes; ++j) {
			this->pEdges[i][j] = edges[i][j];
		}
	}
}

3. 邻接表怎么存

邻接矩阵查边很快，但它有个明显的毛病。不管两个顶点之间到底有没有边，矩阵都得给这对顶点留出一个位置。一个图如果顶点很多、边却很少，例如上千个顶点但每个顶点只连两三条边，矩阵里大部分格子都是 0，空间全浪费了。这就是稀疏图的痛点。

邻接表就是冲着这个毛病来的。顶点仍然用一个一维数组存，方便按下标直接取顶点信息。但每个顶点的所有邻接点，因为个数不固定，就用一条单链表串起来。数组管顶点，链表管边，边存在的地方才花空间。

我们还是拿刚才那个 4 顶点的图建邻接表。代码里是按下标从小到大扫矩阵，发现 i 和 j 之间有边，就把 j 这个邻接点插到 i 的链表头上，所以链表的顺序是倒着进来的。建出来每条链从表头到表尾是这样的。V0 的链表挂着 V2、V1。V1 的链表挂着 V3、V2、V0。V2 的链表挂着 V1、V0。V3 的链表挂着 V1。

我们对照矩阵看一眼。V1 在矩阵里连了 V0、V2、V3 三个点，邻接表里 V1 的链表正好三个节点，一个不多一个不少，只是顺序反过来了。无向图每条边会在两个顶点的链表里各出现一次，所以整张表里节点总数是边数的两倍。

//边表节点
class EdgeNode {
public:
	int mAdjvex; //邻接点域，表示连接的是那个顶点
	int mWeight; //权值
	EdgeNode* pNext; //指向边表中下一个节点
};

//顶点节点
template<class VertexType>
class VertexNode {
public:
	EdgeNode* pFirstEdge; //指向边表的第一个节点
	VertexType mVertexData; //顶点数据
};

//邻接表
template<class VertexType>
class AdjacencyList {
public:
	template<class MatrixType>
	AdjacencyList(int numVex, int numEdges, VertexType* vexes, MatrixType edges);
public:
	VertexNode<VertexType>* pVertexes; //指向顶点数组
	int mNumVetexes; //顶点数
	int mNumEdges; //边数
};

template<class VertexType> template<class MatrixType>
AdjacencyList<VertexType>::AdjacencyList(int numVex, int numEdges, VertexType* vexes, MatrixType edges)
{
	this->mNumVetexes = numVex;
	this->mNumEdges = numEdges;

	//创建并初始化顶点数组
	this->pVertexes = new VertexNode<VertexType>[this->mNumVetexes];
	for (int i = 0; i < this->mNumVetexes; ++i) {
		this->pVertexes[i].mVertexData = vexes[i];
		this->pVertexes[i].pFirstEdge = NULL;
	}

	//初始化边集
	for (int i = 0; i < this->mNumVetexes; ++i) {
		for (int j = 0; j < this->mNumVetexes; ++j) {

			//说明顶点i 和顶点j之间有边
			if (edges[i][j] > 0 && edges[i][j] < INT_MAX) {

				//创建新边节点
				EdgeNode* pNode = new EdgeNode;
				pNode->mAdjvex = j; //邻接点
				pNode->mWeight = edges[i][j]; //权值
				pNode->pNext = this->pVertexes[i].pFirstEdge;
				this->pVertexes[i].pFirstEdge = pNode;

			}

		}
	}
}

4. 两种存法对比

两种存法没有绝对的好坏，全看图密不密。我们把上面的分析归拢到一张表，选型的时候对着看就行。

我们拿刚才的小图举例。它只有 4 条边，顶点数也小，两种存法差别看不出来。但如果换成一百万个顶点、每个顶点平均只连三条边的社交网络，邻接矩阵要开一万亿个格子，根本开不出来，邻接表却只存顶点加六百万个边节点，轻松放下。反过来，如果是一个边几乎铺满的稠密图，邻接表的链表指针反而比矩阵数组更费空间。

5. 常见的误区

第一个误区，是以为邻接表里邻接点的顺序有讲究。顺序取决于插入顺序，上面代码是插到表头，所以是倒的，换个插法顺序又不一样。要依赖邻接点顺序写逻辑就会出错，需要有序得自己排序。

第二个误区，是把无向图的边在邻接表里只存一份。无向边 (Vi, Vj) 在 Vi 的链表和 Vj 的链表要各挂一个节点，这就是边节点总数是 2e 的原因。只存一边，从 Vj 出发就找不到 Vi 了。

第三个误区，是忽略有向图的出边和入边之分。上面这套邻接表存的是出边，从 Vi 出发能直接看到它指向谁，但要查谁指向 Vi，就得把整张表扫一遍。有向图需要频繁查入边时，得另外再建一份逆邻接表。

回到开头的问题。存图就是决定把边关系放在哪。邻接矩阵用一个 n 乘 n 的方阵，查边一步到位，但稀疏图浪费空间。邻接表用数组加链表，边存在的地方才花钱，稀疏图省内存，代价是查某条边要顺着链表找。选型就看一点，图密就上矩阵，图疏就上表。把上面那个 4 顶点的小图两种方式都建一遍，矩阵格子和链表节点能对上，这一节就通了。