算法与数据结构【30天】集训营——图的遍历之深度优先搜索、广度优先搜索（28）

深度优先搜索

深度优先搜索遍历类似于树的先序遍历（根左右）

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

深度优先搜索是一个递归的过程 首先，选定一个出发点后进行遍历，如果有邻接的未被访问过的节点则继续前进。若不能继续前进，则回退一步再前进，若回退一步仍然不能前进，则连续回退至可以前进的位置为止。重复此过程，直到所有与选定点相通的所有顶点都被遍历。

深度优先遍历通常借助栈来实现算法

深度优先遍历顺序为 1->2->4->8->5->3->6->7

类似于二叉树的先序遍历思想

具体思想模板案例

图解过程

无向图深度优先搜索

以下图中所示无向图说明深度优先搜索遍历过程

• 首先选取顶点A为起始点，输出A顶点信息，并标记A为已访问顶点
• A的邻接顶点有(同一条边上的两个顶点称之为对方的邻接顶点)C、D、F，从中任意选取一个顶点前进。这里我们选取C顶点为前进位置顶点。输出C顶点信息，并标记C为已访问顶点。当前位置指向顶点C
• 顶点C的邻接顶点有A、D和B，此时A已经标记为已访问顶点，因此不能继续访问。从B或者D中选取一个顶点前进，这里我们选取B顶点为- 前进位置顶点。输出B顶点信息，标记B顶点为已访问顶点。当前位置指向顶点B
• 顶点B的邻接顶点只有C、E，C已被标记，不能继续访问，因此选取E为前进位置顶点，输出E顶点信息，标记E顶点，当前位置指向E
• 顶点E的邻接顶点均已被标记，此时无法继续前进，则需要进行回退。将当前位置回退至顶点B
• 顶点B的邻接顶点也均被标记，需要继续回退，当前位置回退至C
• 顶点C可以前进的顶点位置为D，则输出D顶点信息，并标记D顶点。当前位置指向顶点D
• 顶点D没有前进的顶点位置，因此需要回退操作。将当前位置回退至顶点C
• 顶点C没有前进的顶点位置，继续回退，将当前位置回退至顶点A
• 顶点A前进的顶点位置为F，输出F顶点信息，并标记F。将当前位置指向顶点F
• 顶点F的前进顶点位置为G，输出G顶点信息，并标记G。将当前位置指向顶点G
• 顶点G没有前进顶点位置，回退至F。当前位置指向F
• 顶点F没有前进顶点位置，回退至A，当前位置指向A
• 顶点A没有前进顶点位置，继续回退，发现没有可用回退的顶点，则以A为起始的遍历结束。若图中仍有未被访问的顶点，则选取未访问的- 顶点为起始点，继续执行此过程。直至所有顶点均被访问
• 采用深度优先搜索遍历顺序为A->B->C->D->E->F->G->H

如果看不懂上面的演示，可以先看一下上面的模板案例，理解其思想之后，自己直接就可以写出来这些东西了，把我号他是栈操作即可！

有向图深度优先搜索

• 以顶点A为起始点，输出A，并标记A。当前位置指向A
• 以A为尾的边只有1条，且边的头为顶点B，则前进位置为顶点B，输出B，标记B。当前位置指向B
• 顶点B可以前进的位置有C与F，选取F为前进位置，将F入栈，并标记F。当前位置指向F
• 顶点F的前进位置为G，输出G，并标记G。当前位置指向G
• 顶点G没有可以前进的位置，则回退至F，当前位置指向F
• 顶点F没有可以前进的位置，继续回退至B，当前位置指向B
• 顶点B可以前进位置为C和E，选取E，输出E，并标记E。当前位置指向E
• 顶点E的前进位置为D和B，而B已经被标记为输出过，则输出D，并标记D。当前位置指向D
• 顶点D的前进位置为C，输出C，并标记C。当前位置指向C
• 顶点C没有前进位置，进行回退至D
• 继续执行此过程，发现没有可以回退的顶点，以A为起始点的遍历过程结束。若图中仍有未被访问的顶点，则选取未访问的顶点为起始点，继续执行此过程。直至所有顶点均被访问。
• 输出次序：A、B、F、G、E、D、C

注意，答案不唯一，按照其思想即可

广度优先搜索

参考案例模板

算法思想

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

算法特点

广度优先搜索类似于树的层次遍历，是按照一种由近及远的方式访问图的顶点。在进行广度优先搜索时需要使用队列存储顶点信息。

广度优先遍历通常借助队列来实现算法

图解过程

无向图的广度优先搜索

图所示的无向图，采用广度优先搜索过程。

重点是找到它的邻接顶点

（1）选取A为起始点，输出A，A入队列，标记A，当前位置指向A。

（2）队列头为A，A出队列。A的邻接顶点有B、E，输出B和E，将B和E入队，并标记B、E。当前位置指向A。

（3）队列头为B，B出队列。B的邻接顶点有C、D，输出C、D，将C、D入队列，并标记C、D。当前位置指向B。

（4）队列头为E，E出队列。E的邻接顶点有D、F，但是D已经被标记，因此输出F，将F入队列，并标记F。当前位置指向E。

（5）队列头为C，C出队列。C的邻接顶点有B、D，但B、D均被标记。无元素入队列。当前位置指向C。

（6）队列头为D，D出队列。D的邻接顶点有B、C、E，但是B、C、E均被标记，无元素入队列。当前位置指向D。

（7）队列头为F，F出队列。F的邻接顶点有G、H，输出G、H，将G、H入队列，并标记G、H。当前位置指向F。

（8）队列头为G，G出队列。G的邻接顶点有F，但F已被标记，无元素入队列。当前位置指向G。

（9）队列头为H，H出队列。H的邻接顶点有F，但F已被标记，无元素入队列。当前位置指向H。

（10）队列空，则以A为起始点的遍历结束。若图中仍有未被访问的顶点，则选取未访问的顶点为起始点，继续执行此过程。直至所有顶点均被访问。

则访问次序为：A、B、E、C、D、F、G、H

有向图的广度优先搜索

（1）选取A为起始点，输出A，将A入队列，标记A。

（2）队列头为A，A出队列。以A为尾的边有两条，对应的头分别为B、C，则A的邻接顶点有B、C。输出B、C，将B、C入队列，并标记B、C。

（3）队列头为B，B出队列。B的邻接顶点为C，C已经被标记，因此无新元素入队列。

（4）队列头为C，C出队列。C的邻接顶点有E、F。输出E、F，将E、F入队列，并标记E、F。

（5）队列头为E，E出队列。E的邻接顶点有G、H。输出G、H，将G、H入队列，并标记G、H。

（6）队列头为F，F出队列。F无邻接顶点。

（7）队列头为G，G出队列。G无邻接顶点。

（8）队列头为H，H出队列。H邻接顶点为E，但是E已被标记，无新元素入队列。

（9）队列为空，以A为起始点的遍历过程结束，此时图中仍有D未被访问，则以D为起始点继续遍历。选取D为起始点，输出D，将D入队列，标记D。

（10）队列头为D，D出队列，D的邻接顶点为B，B已被标记，无新元素入队列。

（11）队列为空，且所有元素均被访问，广度优先搜索遍历过程结束。广度优先搜索的输出序列为：A->B->C->E->F->G->H->D。

总结而言，对于有向图的广度搜索就是首先确定好一个起始值，然后寻找其邻接顶点（就是以改点出发的第二个元素）作为其入队的元素，可以按照其大小进行入队（在前面的可以先入），然后就出队，又将出队的邻接顶点的元素入队，然后出队，然后循环，最后直到队列为空即可，最后进行没有访问到的，又开始执行…

总结

总而言之，深度搜索我们可以理解为栈操作，广度搜索我们可以理解为队列操作

每文一语

越是最后，越不应该放弃，加油！