一、介绍

1、为什么要有图

前面学习了线性表和树。线性表局限于一个直接前驱和一个直接后继；树也只能有一个直接前驱。当我们需要表示多对多的关系时，就用到了图。

2.基本概念

① 顶点（vertex） ② 边（edge） ③ 路径 ④ 无向图，顶点之间的连接没有方向。 ⑤ 有向图，顶点之间的连接有方向。 ⑥ 带权图，边带权值，也叫网。

3.图的表示方式

有两种，二维数组表示（邻接矩阵）；链表表示（邻接表）。

二、图的遍历

1.介绍

2.深度优先（DFS）

原理 先从初始访问结点出发，初始访问结点可能有多个领接结点，深度优先遍历的策略就是首先访问第一个领接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个领接结点。然后重复。 步骤 ① 访问初始结点v，并标记结点v已访问 ② 查找结点v的第一个邻接结点w ③ 若w存在，则执行④；若w不存在，直接返回。 ④ 若w未被访问，对w进行深度优先遍历（即把w当作另一个v，然后进行步骤1234）. ⑤ 在④递归中，如果遇到③返回了，则查找结点v的w邻接结点的下一个邻接结点，转到步骤③。 以上步骤只能处理连通图，如果要处理不连通图还要再最外层添加一层循环，循环遍历所有的结点，然后当结点未被访问时，结点都重复一次上述步骤。 代码

3.广度优先（BFS）

原理 类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这个结点的邻接结点。 步骤 ① 访问初始结点v并标记结点v为已访问。 ② 结点v入队列。 ③ 当队列非空时，继续执行，否则算法结束。 ④ 出队列，取得队头结点u。 ⑤ 查找结点u的第一个邻接结点w。 ⑥ 若w不存在，则转到步骤3；否则循环执行一下2个步骤。 6.1 若结点w尚未访问，则访问结点w并标记为已访问。结点w入队列. 6.2 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6 同理，以上步骤适用于连通图，非连通图需要整体循环。 代码

4.DFS和BFS区别

①广度优先搜索使用队列数据结构来存储未探索的结点。深度优先搜索使用堆栈数据结构存储未探索的结点。 ② BFS较慢，需要更多的内存；DFS更快并且更少的内存。 ③ DFS规模不能太大，应为使用堆栈。