数据结构与算法之图的深度优先遍历和广度优先遍历

图是表示一种多对多关系的数据结构
它包括无向图，有向图，带权图

无向图：就是顶点之间的连线（边）没有方向箭头

有向图：就是顶点之间的连线（边）有方向箭头

带权图：就是顶点之间的连线（边）表明了大小如上海到北京的距离，北京到天津的距离类似的导航地图就是带权图

下图就是一个无向图：
字母所表示的是顶点，顶点间的连线叫做边

按照A,B,C,D,E,F,G的顺序添加节点，并添加对应的边构成下图

深度优先遍历：

从初始访问结点出发，我们知道初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点。总结起来可以这样说：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。

具体算法表述如下：

1.访问初始结点v，并标记结点v为已访问。
2.查找结点v的第一个邻接结点w。
3.若w存在，则继续执行4，否则算法结束。
4.若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤123）。
5.查找结点v的w邻接结点的下一个邻接结点，转到步骤3。

按照上图便利的顺序应该是A->B->C->G->D->E->F->

广度优先遍历：
类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点。

具体算法表述如下：

1.访问初始结点v并标记结点v为已访问。
2.结点v入队列
3.当队列非空时，继续执行，否则算法结束。
4.出队列，取得队头结点u。
5.查找结点u的第一个邻接结点w。
6.若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个步骤：
1). 若结点w尚未被访问，则访问结点w并标记为已访问。
2). 结点w入队列
3). 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6。

按照上图便利的顺序应该是A->B->C->D->E->G->F->