图

顶点（vertex)

边（edge）

简单实现： 邻接矩阵实现

1
2
3
4
5
6
7
8

0 # 1 2 3 4 5 6		第一行 第一列代表节点
###############
1 # 0 1 0 0 1 0		如果 表中值为1则代表这两
2 # 1 0 1 1 1 1 	个顶点通路
3 # 0 0 1 0 1 0		2 --> 1 代表顶点1 到    
4 # 0 1 0 1 0 1		顶点2通路
5 # 1 0 1 0 1 0
6 # 1 1 0 1 0 1

更高效的实现方法是：邻接列表

维护一个包含所有顶点的主列表

1
2
3
4
5
6
7
8

[
v0,  -------->  {V1:5,v5:2}
v1,  -------->  {v2:4}
v2,  -------->  {v3:2}
v3,  -------->  {v4:7}
v4,  -------->  
v5   -------->
]# 主列表

广度优先算法Breadth First Search（BFS）

类似与一层一层的遍历

先选择一条路径，走到最深处，若不匹配就回溯知道有另一条路径，知道找到匹配的值

所以bfs

需要三个特有属性

1. 顶点回溯
2. 顶点标记（如为走过： 白色 走过： 黑色 当前顶点：红色）

图的应用

寻路、词阶。