数据结构与算法之图的概念、存储结构及遍历方式
一、图的概念
1、图：图（graph）由边（edge）的集合及顶点（vertex）的集合组成。通常记为：G=(V,E)。
2、有向图、无向图
图根据边有无方向分为有向图和无向图。
3、邻接点、入边、出边
邻接点：一条边上的两个顶点叫做邻接点。
在有向图中，除了邻接点之外，还有“入边”和“出边”的概念。
入边：是指以该顶点为终点的边；
出边：指以该顶点为起点的边。
例如：
在上面的无向图中，顶点A和顶点B就是邻接点；
在上面的有向图中，是A的出边、B的入边。
4、度：一个顶点的度是指与该顶点相关联的边的条数，顶点v的度记作d(v)。
对于有向图来说，一个顶点的度可细分为入度和出度。
入度：一个顶点的入度是指与其关联的各边之中，以其为终点的边数；
出度：出度则是相对的概念，指以该顶点为起点的边数。
例如：
在上面的无向图中，顶点A的度为2，顶点C的度为3，顶点D的度为1；
在上面的有向图中，顶点A的入度是0，出度是2；顶点B的入度是1，出度是2；顶点C的入度是2，出度是2。
二、图的存储结构
图的存储结构主要有邻接矩阵、邻接表、十字链表、多重链表，最常用的是邻接矩阵和邻接表。
三、图的遍历
图的遍历是指从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历分为深度优先遍历和广度优先遍历。
| 有向图 | 无向图 | |
| 定义 | 图中的每条边都是有方向的。 | 图中的每条边都是无方向的。 |
| 示例图 |
|
|
| 说明 |
G=(V1,{E1})，其中：
V1={A, B, C, D, E, F}，V1表示由"A,B,C,D,E,F"几个顶点组成的集合。
E1={ |
G=(V2,{E2})，其中： V2={A, B, C, D, E, F}，V2表示由"A,B,C,D,E,F"几个顶点组成的集合。 E2={(A, B), (A, C), (B, C), (B, E), (C, D), (C, F), (E, F)}。E2是由边(A,B),边(A,C)...等组成的集合。其中，(A,C)表示由顶点A和顶点C连接成的边。 |
| 邻接矩阵 | 邻接表 | |
| 定义 |
邻接矩阵是表示顶点之间相邻关系的矩阵。设图G有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：
|
当图中的边数较少时，用邻接矩阵来实现图结构会浪费很多内存空间，使用邻接表更省空间。 |
|
示例图（无向图）
|
|
|
|
示例图（有向图）
|
|
|
| 优点 | 可以直接判断两顶点之间是否有边或弧，速度很快。 一般用于存储稠密图。 | 空间效率高；容易寻找顶点的邻接点。 一般用于存储稀疏图。 |
| 缺点 | 存储空间大，会影响算法的空间效率，甚至时间效率。 | 判断两顶点之间是否有边或弧需搜索两节点对应的单链表，没有邻接矩阵方便。 |
| 深度优先遍历（Depth-First-Search, DFS） | 广度优先遍历（Breadth-First-Search, BFS） | |
| 方法 | ①访问顶点v； ②依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问； ③若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。 | ① 访问顶点vi； ② 访问vi的所有未被访问的邻接点w1 ,w2 , …wk； ③ 依次从这些邻接点（在步骤②中访问的顶点）出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问。 |
| 示例图 |
|
|
| 步骤 | DFS在访问图中某一起始顶点A后，由A出发，访问它的任一邻接顶点B； 从B出发，访问与B邻接但还没有访问过的顶点E； 从E出发，访问与E邻接但还没有访问过的顶点G； 因为G的邻接顶点都已被访问，所以退回到顶点E； 因为E的邻接顶点都已被访问，所以退回到顶点B； 因为B有未访问的邻接顶点C，则从B出发，访问C； 从C出发，访问与C邻接但还没有访问过的顶点F； 从F出发，访问与F邻接但还没有访问过的顶点D（也可以先访问H）； 因为D的邻接顶点都已被访问，所以退回到顶点F； 因为F有未访问的邻接顶点H，则从F出发，访问H； 从H出发，访问与H邻接但还没有访问过的顶点I； 因为I的邻接顶点都已被访问，所以退回到顶点H； 因为H的邻接顶点都已被访问，所以退回到顶点F； 因为F的邻接顶点都已被访问，所以退回到顶点C； 因为C的邻接顶点都已被访问，所以退回到顶点B； 因为B的邻接顶点都已被访问，所以退回到顶点A； 所有顶点都被访问过，遍历结束。 | BFS在访问图中某一起始顶点A后，由A出发，依次访问它的邻接顶点B、C、D； 因为先访问的B，所以从B出发，访问与B邻接但还没有访问过的顶点E； 从C出发，访问与C邻接但还没有访问过的顶点F； 因为D的邻接顶点均被访问，所以从E出发，访问与E邻接但还没有访问过的顶点G； 从E出发，访问与F邻接但还没有访问过的顶点H； 从H出发，访问与H邻接但还没有访问过的顶点I； 所有顶点都被访问过，遍历结束。 |
| 结果 | A→B→E→G→C→F→D→H→I | A→B→C→D→E→F→G→H→I |