图的表示
邻接矩阵（Adjacency Matrix）
拥有n个顶点的简单有向图（没有自环和重边），它所包含的边的数量最多是n(n-1)条；简单无向图最多有n(n-1)/2条边，因此，要表达各个顶点之间的关联关系，最清晰易懂的方式是使用邻接矩阵G[N][N]。
对于无向图来说，如果顶点之间有关联，那么邻接矩阵中对应的值为1；如果顶点之间没有关联，那么邻接矩阵中对应的值为0。
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 0 | 1 | 0 | 1 | 0 |
| B | 1 | 0 | 1 | 0 | 0 |
| C | 0 | 1 | 0 | 1 | 1 |
| D | 1 | 0 | 1 | 0 | 0 |
| E | 0 | 0 | 1 | 0 | 0 |
需要注意的是，邻接矩阵从左上到右下的一条对角线上的元素值必然是0，因为此处讨论的简单图没有自环。同时，无向图对应的邻接矩阵是一个对称矩阵，假如A和B有关联，那么B和A也必定有关联。
但是对于有向图的邻接矩阵，不一定是一个对称矩阵，假如A可以达到B，从B未必能达到A。
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 0 | 0 | 0 | 0 |
| C | 0 | 0 | 0 | 1 |
| D | 0 | 1 | 1 | 0 |
对于网络，只要把邻接矩阵对应位置的值定义为边的权重即可。
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 5 | 2 | ||||
| B | 4 | |||||
| C | 9 | |||||
| D | 7 | 3 | ||||
| E | 1 | |||||
| F | 1 | 8 |
对于带权图，如果不同的顶点和之间没有边应该将权值设为。初始化最短路径距离矩阵时，主对角线设为0。
邻接矩阵的优点：
-
简单、直观。
-
可以快速查到一个顶点和另一顶点之间的关联关系。
-
方便计算任一顶点的度，对于有向图，从顶点发出的边数为出度，指向顶点的边数为入度。
邻接矩阵的缺点：
-
浪费空间，对于稀疏图（点很多而边很少）有大量无效元素。但对于稠密图（特别是完全图）还是很合算的。
-
浪费时间，统计稀疏图中边的个数，也就是计算邻接矩阵中元素1的个数。
知识测验
邻接表（Adjacency List）
为了解决邻接矩阵占用空间的问题，人们想到了另一种图的表示方法——邻接表。在邻接表中，图的每一个顶点都是一个链表的头结点，其后连接着该顶点能够直接到达的相邻顶点。对于稀疏图而言，邻接表存储方式占用的空间比邻接矩阵要小得多。
同一张图的三种存储视图
解锁完整互动实验、进阶解析与精选参考答案。
通过遍历邻接表可以查找到所有能够到达的相邻顶点，但是对于逆向查找，即哪些顶点可以达到一个顶点就会很麻烦。
逆邻接表和邻接表是正好相反的，逆邻接表每一个顶点作为链表的头结点，后继结点所存储的是能够直接到达该顶点的相邻顶点。
可是，一个图要维护正反两个邻接表，也太麻烦了吧？
通过十字链表可以把邻接表和逆邻接表结合在一起。
知识测验
把有向边写成矩阵与链表
顶点按A、B、C、D排列，边为A→B、A→D、C→A、C→D、D→B。画图，写出邻接矩阵（行是起点），再画邻接表与逆邻接表，说明B为什么没有出边链却有两个入边结点。