导语：「算法」DFS(Depth First Search)，了解一下深度优先遍历的大概

DFS(Depth First Search)，叫做深度优先遍历，顾名思义，就是对每一个可能的分支路径走到底，而且每个节点只能访问一次。

深度优先遍历的方法是：从图中给定的某个顶点A出发，依次从顶点A附近的未访问的邻接点出发，对图进行深度优先遍历，直到图中和顶点A有路径想通的节点都访问过为止。

如果此时图中仍有其他的顶点没有被访问过，那就从这个未被访问过的顶点开始，再度进行深度优先遍历，直到图中所有的顶点都被访问为止。

无向图的深度优先遍历

图一

如图所示，这是一张无向图，我们给定从顶点A出发，来进行深度优先遍历搜索，能够得到哪些结果。

显而易见，A、B、E、D、F、C，一轮下来就走完了，那这就是该无向图的深度优先遍历得到的结果。

有向图的深度优先遍历

图二

如图所示，这是一张有向图，对于有向图而言，深度优先遍历搜索也是一样的道理，按照箭头的方向进行遍历。

可以得到A、C、F、E、D，此时可以发现节点B还没有遍历到，因此，最后遍历节点B。

最短路径算法

最短路径算法：从某个顶点出发，沿图的边到达另一个顶点所经过的路径中，各条边上的权值最小的一条路径就是最短路径。

比方说，以我给出的有向图为例子，求节点A到节点D的最短路径。

我们可以写出节点A到节点D有如下几条路径：

1、A、D 距离为30

2、A、C、F、D 距离为5+7+10=22

3、A、C、F、E、D 距离为5+7+18+4=34

4、A、C、B、E、D 距离为5+15+8+4=32

最后可以很清楚的看到，最短路径为A、C、F、D，最短的距离为22。

免责声明:本站部份内容由优秀作者和原创用户编辑投稿，本站仅提供存储服务，不拥有所有权,不承担法律责任。若涉嫌侵权/违法的，请反馈，一经查实立刻删除内容。本文内容由快快网络小涵创作整理编辑！