图的表示
如图所示为一个图
图上的节点(V 表示)之间的边(E表示) 是没有方向的又称为无向图
要表示一个图 G = (V,E) 有临近表表示法和临近矩阵表示法
临近表表示方法
如图所示，是一个有|V|个列表的数组Adj所组成，每个列表对应于V中的一个顶点。对于每一个u ∈ V，临近表 Adj[u] 包含所有满足条件(u,v) ∈ E 的顶点v。第一行表示顶点 0 与顶点1，4 有一条边。第二行表示顶点1 与顶点 0,2,3,4有一条边。第三行表示订单 2 与顶点1，3 有一条边。
由上表示方法临近表表示法也可以表示有向图。比如第一行。表示顶点0到顶点1有一条边和顶点0到顶点4有一条边。至于顶点1到顶点0是否有边则需要看 Adj[1] 行的数据。
临近矩阵表示方法
在矩阵表 是一个|V|x|V| 的矩阵 A 满足， 如果(i,j) ∈ E 则 a(i,j) = 1 否则 a(i,j) = 0。
临近表表示方法适用于稀疏图，临近矩阵表示方法使用稠密图
广度优先搜索
在给定图 G = (V, E) 和一个特定的源顶点 s 的情况下，广度优先搜索系统的探索 G 中的边，以发现可以从 s 到达的所有顶点，并计算 s 到所有这些可达顶点之间的距离(即最少边数)。该搜索方法同时还能生成一颗根为 s、且包含所有 s 的可达顶点的广度优先树。
该方法之所以称为广度优先搜索。是因为它始终将已发现和未发现之间的边界，沿其广度方向向外扩展。亦即，算法首先会发现和 s 距离为 k 的所有顶点, 然后才会发现和 s 距离为 k + 1 的其他顶点。
为了记录搜索轨迹，广度优先搜索将每个顶点都着色为白色，灰色，黑色。算法开始时所有的点都是白色；随着搜索的进行，给个顶点会逐渐变为灰色，黑色。该算法还使用先进先出的对接 Q 来管理所有灰色的顶点。
搜索过程如图所示：
初始步骤：所有顶点初始化为白色，队列为空
第一步： 设置顶点0设为灰色, 队列 Q 中 添加 顶点 0
第二步：从队列 Q 中取出 0。与节点 0 关联的节点 1 , 4。此时1，4都是白色。 设置1，4为灰色，并 将 1,4加入 Q 中。最后将0设置为黑色。由于Q 中已经取出0，所以此时Q 中只有 [1,4]。
第三步：从队列中取出1，与1 相邻的节点有 2，3，4。此时只有2，3为白色。所以只将2，3加入队列并设置为灰色，将1设置为黑色。此时队列中 [4,2,3]。
第四步：从队列中取出4, 与4 相邻 有0，1，3。但无白色顶点。将4设置为黑色。此时队列中为[2,3]
第五步：从队列中取出2，与2相邻1，3，但均无白色，将2设置为黑色完成。此时队列中为[3]
第六步: 从对接中取出3, 与3相邻4，1，2 均无白色。将3设置为黑色。此时队列为空搜索完成。
Go语言版 广度优先搜索代码如下：
代码中 color 记录节点颜色。d 记录顶点到所有节点之间的最小距离。p 记录节点的父节点。p 可生成一颗广度优先树。根节点为顶点
const (
WHITE = 0 //白色
GRAY = 1 //灰色
BLACK = 2 //黑色
)
//图的广度优先搜索
func graphBreadthFirstSearch(graph [][]int, s int) (color []int, d []int, p []int) {
color = make([]int, len(graph))
d = make([]int, len(graph))
p = make([]int, len(graph))
for i := 0; i < len(graph); i++ {
color[i] = WHITE
d[i] = -1
p[i] = -1
}
//初始化第一个节点
color[s] = GRAY
d[s] = 0
p[s] = -1
queue := make([]int, 1)
queue[0] = s
for ; len(queue) > 0; {
u := queue[0]
queue = queue[1:]
for _, v := range graph[u] {
if color[v] != WHITE {
continue
}
vInQueue := false
for _, q := range queue {
if v == q {
vInQueue = true
break
}
}
if !vInQueue {
queue = append(queue, v)
}
color[v] = GRAY
d[v] = d[u] + 1
p[v] = u
}
color[u] = BLACK
}
return
}
深度优先搜索
深度优先搜索遵循的搜索策略是尽可能“深”的搜索一个图。在深度搜索中，对于新发现的顶点，如果它还有此为起点而未探测到的边，就沿此边继续探测下去。当顶点v的所有边都被探测之后，搜索将回溯到发现顶点v有起始点的那些边。这一过程一直进行到已发现从源顶点可达的所有顶点为止。如果还存在未被发现的顶点，则选择其中的一个作为源顶点，重复以上过程，直到所有的顶点都已被发现为止。
与广度搜索类似，在深度搜索中，每当扫描已发现的顶点 u 的邻近表，从而发现新顶点 v 时，就将 v 的先辈域 π[v] = u。由于搜索可能是多个源顶点开始重复进行。所以深度优先的先辈子图可能有多棵树组成。
与广度优先类似，深度优先也通过对顶点找色来区分顶点状态。开始时顶点均为白色，搜索发现时为灰色，结束时又被置为黑色。这一技巧可以保证每一个顶点在搜索结束时，只存在于一颗深度优先树中，因此这些树是不相交的。
除此之外，深度优先为每个顶点 v 加盖时间戳，每个顶点 v 有两个时间戳 d[v] 表示第一次被发现的时间戳，f[v] 表示结束检查 v 时的时间戳。因此总有 d[v] < f[v]
深度优先搜索过程如下图所示
起始点位置不一样，结果也会不同，此图只是一种结果
生成树中标为B,F,C 类型的边不是树边 在树中不应该存在
深度优先搜索生成的深度优先树中可以把边分为如下四类
第一类：树边，在图中的边，应用于生成树中的边
第二类：反向边，顶点 u 到他的某一个祖先的顶点 v 的边 如图中 标位B的边，自循环边也认为是反向边
第三类：正向边，顶点 u 到他的某一个后裔 v 的 非树边，图中标位 F 的边
第四类：交叉边，其他类型边，u,v 之间 u既不是 v 的祖先也不是 v 的后裔。图中标位 C 类的边
Go语言版 深度优先搜索代码如下：
type Graph struct {
G map[string][]string
D map[string]int
F map[string]int
P map[string]string
Color map[string]int
time int
}
func (graph *Graph) Init(g map[string][]string) {
graph.G = g
graph.Color = make(map[string]int, len(g))
graph.D = make(map[string]int, len(g))
graph.F = make(map[string]int, len(g))
graph.P = make(map[string]string, len(g))
graph.time = 0
for u := range g {
graph.Color[u] = WHITE
graph.D[u] = -1
graph.F[u] = -1
graph.P[u] = "0"
}
}
//图的深度优先搜索
func (graph *Graph) dfs() {
if graph.Color["s"] == WHITE {
graph.dfsVisit("s")
}
for u := range graph.G {
if graph.Color[u] == WHITE {
graph.dfsVisit(u)
}
}
}
func (graph *Graph) dfsVisit(u string) {
graph.time = graph.time + 1
graph.D[u] = graph.time
graph.Color[u] = GRAY
for _, v := range graph.G[u] {
if graph.Color[v] == WHITE {
graph.P[v] = u
graph.dfsVisit(v)
}
}
graph.Color[u] = BLACK
graph.time = graph.time + 1
graph.F[u] = graph.time
}
