数据结构-什么是图和图的遍历

什么是图？

图：表示多对多的关系。
包含：

• 一组顶点：通常用V(Vertex)表示的顶点集合

• 一组边：通常E(Edge)表示边的集合，也就是顶点对

  • 无向边：v — w 两个顶点之间无论任何方向都可以连通 ，常用( v, w )表示
  • 有向边：v —> w 也就是只允许从顶点A到顶点B，常用< v, w >表示
  • 不考虑重边和自回路

图的存储结构

1、邻接矩阵表示法

我表示看不懂

2、邻接表表示法

图的遍历

1、深度优先搜索DFS （Depth First Search）

现在用点亮灯泡的方式模拟遍历
步骤如下：

1. 先点亮入口处A的灯，然后站在A处后发现有B和E两处灯光未点亮
2. 选择点亮B，站在B处后发现C未点亮…
3. 此处省略相同步骤，点亮D处的灯后发现面前有E、G、H三处未点亮
4. 选择点亮E，站在E处发现有A和F，A已经点亮了
5. 选择点亮F，然后发现到头了，视野中所有的灯都亮着。此时不能直接结束点亮工作。
6. 选择原路返回，并检查每个顶点是不是还有未点亮的灯，如果灯全部都亮了则继续返回
7. 退回到D后，发现还有G、H没亮
8. 选择点亮G，然后到H
9. 点亮到H之后发现视野中A、G、D的灯全部都亮着，于是继续返回，并检查
10. 退回路径G-D-C-B-A，流程结束

其实看到这整个流程，我脑子里第一想法是这不是个堆栈嘛，点亮一个就入栈一个，然后视野中全部点亮了就出栈。
伪代码实现，采用递归方式

2、广度优先搜索（Breadth First Search）

广度优先搜索使用了队列，大概步骤分为：

1. 先把1压入队列，然后做出队操作，1出队
2. 把1直接相关的顶点，234567做入队操作
3. 然后出队操作，2出队
4. 把2相关的顶点8，9做入队操作
5. 然后出队操作，3出队
6. 把3相关的顶点10做入队操作
7. 然后依次出队把34567相关的顶点做入队操作
8. 然后出队…
9. 后面省略，大概就是这么个过程直到队列里没有元素为止

伪代码实现 ：