链接：图的两种遍历方式

树的遍历：

  • 先序遍历
  • 中序遍历
  • 后序遍历
  • 层次遍历

图的遍历：
从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。遍历过程中得到的顶点序列称为图遍历序列。

有两种搜索策略：

深度优先搜索DFS

1、思想

假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

2、特点

递归过程带有回退操作，所以需要用栈存储访问的路径信息，当访问到的当前顶点没有可以前进的邻接顶点时，需要进行出栈操作，将当前位置回退到出栈元素位置

3、无向图的深度优先搜索

图片说明

  1. 从A开始，输出A，将A入栈，标记为已访问
  2. 选取C\D\F中一个前进，选取C，c入栈，标记c
  3. 取A\B\D中一个，但是A已访问，则选取B
  4. 取E
  5. E的邻接顶点均已经被标记，回退，回退至B，且将E出栈
  6. 回退至C，取D
  7. 回退至c，回退至A，取F
  8. 取G，回退至f，回退至a，栈为空

4、有向图的深度优先搜索

图片说明

  1. 从A开始，输出a，标记a，a入栈
  2. 指向b，输出b
  3. 取C\E\F一个，取F
  4. 取G，回退至B，取C\E，取E
  5. 取D、c
  6. 回退至A，栈为空

5、算法分析

  • 当图采用邻接矩阵存储时，由于矩阵元素个数为n^2，因此时间复杂度就是O(n^2)。

  • 当图采用邻接表存储时，邻接表中只是存储了边结点(e条边，无向图也只是2e个结点)，加上表头结点为n（也就是顶点个数），因此时间复杂度为O(n+e)。

广度优先搜索BFS

1、思想

广度优先搜索思想：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。

2、无向图的广度优先搜索

图片说明
A->B->E->C->D->F->G->H

3、有向图的广度优先

图片说明
A->B->C->E->F->H->G
D为起始点重新开始
则A->B->C->E->F->H->G->D