1
数组、链表、栈、队列  →  线性数据结构
2
树                    →  非线性数据结构（层次结构）
3
图                    →  另一种非线性数据结构

1
N 个节点的树必定恰好有 N−1 条边
2
从根出发必须能到达所有节点，且根到某节点只有唯一一条路径

1
图 G = (V, E)
2
V 是顶点集，E 是边集
3
这是一个「有序对」（第一个对象必须是顶点集，第二个必须是边集）

1
有序对 (a, b)：顺序重要，(a,b) ≠ (b,a)（除非 a = b），写成圆括号
2
无序对 {a, b}：顺序不重要，{a,b} = {b,a}，写成花括号

1
不计权重：经 B、C 的路线与经 E、F 的路线都是 3 条边，「同样好」
2
          经 E 的黄色路线只有 2 条边，「最好」
3
计入权重：需要把路径上各边权重相加算总成本
4
          → 最短（最优）路线变成经 B 和 C 的那条

1
|V| 表示顶点数量
2
|E| 表示边的数量
3
（集合的基数，用与绝对值相同的记号）

1
自环（self-loop）    一条边只涉及一个顶点、两个端点相同
2
                     例：网页指向自己的链接（点击页眉链接只是刷新）
3
多重边（multi-edge） 同一条边在图中出现不止一次
4
                     例：城市间航班网络（一对城市间有多趟航班）

1
有向图顶点数 = 10  →  最大 90 条边
2
有向图顶点数 = 100 →  最大 9900 条边
3
→ 最大边数近似于顶点数量的平方

1
路径（path）           一系列顶点序列，其中每一对相邻顶点之间都有边相连
2
简单路径（simple path） 没有重复顶点（顶点不重复则边也不会重复）
3
漫步（walk）            允许重复顶点/边
4
轨迹（trail）           顶点可以重复但边不能重复的漫步

1
闭合行走（closed walk）：起点和终点是同一个顶点，且长度必须大于 0
2
长度：路径中边的数量
3
简单环（simple cycle）：闭合行走，且除起点/终点顶点外没有其他顶点或边被重复
4
无环图（acyclic）：不含环的图

1
树中可以有闭合行走（边的重复），但不存在简单环
2
此外树还必须连通（无向无环图不只有树这一种）

1
问题：若边对象前两个字段存字符串，各行长度不同，每行占用内存不一样
2

3
优化 1：字段存「指向顶点列表中那些名称的引用/指针」
4
        → 每行内存相同，且引用比名称副本省很多开销
5

6
优化 2（更好的做法）：只存顶点在顶点列表中的「索引（整数）」
7
        → 边对象的两个字段变成两个整数字段
8
        → 边列表中每一行消耗的内存量都相同

1
顶点列表：O(|V|)
2
边列表（用索引/引用设计）：O(|E|)
3
整体：O(|V| + |E|)

1
|E| 最坏 ≈ V²
2
任何以边数为量级运行的操作都被认为代价很高
3
我们希望把成本控制在「与顶点数量同量级」
4
O(V) 比 O(E) 好得多

1
每个顶点有一个 0 到 V−1 的索引（从顶点列表中取索引：A=0、B=1、C=2…）
2
无权图：A[i][j] = 1 表示存在从 i 到 j 的边，否则为 0

1
A[i][j] 直接存该边的权重
2
不存在的边要设一个默认值，例如一个非常大或最大可能的整数值（图中填的是「无穷」）
3
「这种值绝不会被预期成为边的权重」

1
邻接矩阵确切使用 V² 个单位的内存  →  空间复杂度 O(V²)
2
矩阵不仅存了「相连」的信息，还存了「未相连」的冗余信息

1
假设有 10 亿（10⁹）用户
2
平均一名用户的朋友数不超过 1000
3
连接总数 = 10⁹ × 1000 = 10¹²
4
无向图要除以 2（否则每条边算两次）→ 5 × 10¹¹ 条边
5
这远远少于顶点数量的平方（10¹⁸）
6

7
邻接矩阵需要 10¹⁸ 个存储单元 ≈ 10¹⁸ 字节 ≈ 1000 PB（拍字节）
8
  → 绝不可能装在一块物理磁盘上
9
邻接表只要 5 × 10¹¹ 字节 = 0.5 TB（太字节）
10
  → 如今一台典型个人电脑就会有这么大的存储空间

1
0 号节点连 1、2、3
2
1 号节点连 0、4、5
3
2 号节点连 0、6
4
…
5
7 号节点有 4 个连接（3、4、5、6）
6

7
各行的连接数分别是：0 号 3 个、1 号 3 个、2 号 2 个…… 每行大小都不同

1
C/C++：创建一个「指针数组」，大小为 8
2
       每个指针指向一个不同大小的一维数组
3
       第 0 个指针 → 大小 3 的数组
4
       第 7 个指针 → 大小 4 的数组

1
无向图：2 × |E| 个单位内存
2
有向图：|E| 个单位内存

1
社交网络有 10 亿（10⁹）用户
2
任何人拥有朋友的最大数量是 1 万（10⁴）
3
机器每秒能扫描/读取 10⁶ 个单元

1
每行改成一个链表：不再需要动态改数组大小，插入和删除容易得多
2

3
实现：为每个节点创建一个链表存储其邻居
4
      创建一个「指针数组」，唯一区别是每个指针指向一个「链表的头部」
5
      链表节点有两个域：一个存数据，一个存下一个节点的地址
6
      加权图 → 在节点里再加一个字段存权重