1、图的表示
图的表示
G = ( V , E ) G=(V,E) G=(V,E)
图G由结点的集合V 和 边的集合E 组成
可以用两种方法表示，一种是邻接链表（下图b），一种是邻接矩阵（下图c）。
邻接链表一般用于表示稀疏图（边数 ∣ E ∣ |E| ∣E∣远小于 ∣ V ∣ 2 |V|^2 ∣V∣2），默认都使用邻接链表表示。在稠密图（ ∣ E ∣ |E| ∣E∣接近 ∣ V ∣ 2 |V|^2 ∣V∣2）的情况下，倾向使用邻接矩阵。
无向图：
有向图：
邻接链表表示
由一个链表数组 A d j Adj Adj组成，数组大小为 ∣ V ∣ |V| ∣V∣，链表 A d j [ u ] Adj[u] Adj[u]存储了结点 u u u出发的边的终点。
比如上面无向图中，从结点1出发有两条边，边的终点分别是2和4，反应到邻接链表中就是 A d j [ 1 ] Adj[1] Adj[1]存储了两个节点2和4。
邻接链表需要的存储空间为 O ( ∣ V ∣ + ∣ E ∣ ) O(|V|+|E|) O(∣V∣+∣E∣)
邻接矩阵表示
由一个 ∣ V ∣ × ∣ V ∣ |V|×|V| ∣V∣×∣V∣的矩阵 A = ( a i j ) A=(a_{ij}) A=(aij)表示，并满足以下条件：
a i j = { 1 i f ( i , j ) ∈ E , 0 o t h e r , a_{ij} = \left \{ \begin{aligned} & 1 & if (i, j) \in E, &\\ & 0 & other, & \end{aligned} \right. aij={10if(i,j)∈E,other,
当边有权重时， a i j a_{ij} aij可以存储权重值。
邻接矩阵需要的存储空间为 O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2)
一些术语
一个结点的出度为，从这个结点触发的边的个数。
一个结点的入度为，到达这个结点的边的个数。
2、深度优先搜索
基本思想：尽可能的深入。总是对最近发现的结点 v v v出发的边进行探索，直到结点 v v v出发的边全部被发现时，回溯到 v v v的前驱结点继续探索，直到从源节点出发所有可以到达的结点都被发现。这时如果还有未被搜索的结点，则再随机找一个未被搜索的结点作为源节点进行搜索。
因为可能从一个源节点出发不能搜索到所有结点，所以深度优先搜索会产生多个深度优先树组成深度优先深林。
辅助的给每个结点加入四个属性：
- c o l o r color color：白色表示还未被搜索，灰色表示已被发现但出发的边还没搜索完，黑色表示已被发现并且出发的边已被搜索完
- d d d：该节点的发现时间
- f f f：该结点出发搜索结束的时间
- π π π：该结点的前驱（结点第一次被发现时，正在查询的结点）
下面是深度优先搜索的伪代码和事例：
结点中的x/y表示该结点的发现时间为x，完成时间为y
图中树边被标记为灰色，向前，横向，向前的边分别被标记为B, C, F
深度优先搜索的性质
（1）括号花定理
如上图b所示，每个结点的发现时间和完成时间组成一个括号花结构。
对于两个结点u和v，如果区间[u.d, u.f] 和 [v.d, v.f] 不相交，则u不是v的后代，v也不是u的后代；
如果[u.d, u.f] 包含在 [v.d, v.f] 内，则u是v后代，反之亦然。
（2）白色路径定理
如果结点v是u的后代，当u.d时间时，存在一条从u到v全部由白色结点组成的路径。
3、广度优先搜索
基本思路：利用一个队列，首先将头结点插入队列，循环的取出队列中的一个结点，并
将于该结点相连的结点加入队列，直到队列变空，搜索结束。
辅助的给每个结点加入三个属性：
- color：白色表示还未被搜索，灰色表示加入队列，黑色表示从队列里出来
- d：该节点在第几轮被发现
- ππ：该结点的前驱（结点第一次被发现时，正在查询的结点）
下面是广度优先搜索的伪代码和示例：
广度优先搜索的性质
（1）最短路径
从某个结点u做广度优先搜索，可以找出这个结点到其他结点的最短路径。
结点v和结点u的最短路径距离为v.d
从结点v开始 循环列举前驱结点，就是结点v和结点u的最短路径中经过的结点。
（2）广度优先树
广度优先搜算中，我们在π属性中存储了每个结点的前驱结点，另前驱结点作为该结点的父节点，我们可以得到一个广度优先树。发现新结点的边为树边。