数据结构，简称“DFS”，是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率，数据结构往往同高效的检索算法和索引技术有关。
在计算机科学中，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。“数据结构”作为一门独立的课程，在国际上是从1968年才开始设立的，1968年美国唐纳德·克努特教授
基本算法——深度优先搜索（DFS）和广度优先搜索（BFS）
深度优先搜索和广度优先搜索，都是图形搜索算法，它两相似，又却不同，在应用上也被用到不同的地方。这里拿一起讨论，方便比较。一、深度优先搜索
深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS即Depth First Search。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。
基本步奏
（1）对于下面的树而言，DFS方法首先从根节点1开始，其搜索节点顺序是1,2,3,4,5,6,7,8（假定左分枝和右分枝中优先选择左分枝）。
（2）从stack中访问栈顶的点；
（3）找出与此点邻接的且尚未遍历的点，进行标记，然后放入stack中，依次进行；
（4）如果此点没有尚未遍历的邻接点，则将此点从stack中弹出，再按照（3）依次进行；
（5）直到遍历完整个树，stack里的元素都将弹出，最后栈为空，DFS遍历完成。
二、广度优先搜索
广度优先搜索（也称宽度优先搜索，缩写BFS，以下采用广度来描述）是连通图的一种遍历算法这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。基本过程，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现BFS算法。
基本步奏
（1）给出一连通图，如图，初始化全是白色（未访问）；
（2）搜索起点V1（灰色）；
（3）已搜索V1（黑色），即将搜索V2，V3，V4（标灰）；
（4）对V2，V3，V4重复以上操作；
（5）直到终点V7被染灰，终止；
（6）最短路径为V1，V4，V7.
图遍历算法之DFS/BFS
在计算机科学， 图遍历（Tree Traversal，也称图搜索）是一系列图搜索的算法， 是单次访问树结构类型数据（tree data structure)中每个节点以便检查或更新的一系列机制。图遍历算法可以按照节点访问顺序进行分类，根据访问目的或使用场景的不同，算法大致可分为28种：图遍历即以特定方式访问图中所有节点，给定节点下有多种可能的搜索路径。假定以顺序方式进行（非并行），还未访问的节点就需通过堆栈（LIFO）或队列（FIFO）规则来确定访问先后。由于树结构是一种递归的数据结构，在清晰的定义下，未访问节点可存储在调用堆栈中。本文介绍了图遍历领域最流行的广度优先搜索算法BFS和深度优先搜索算法DFS，对其原理、应用及实现进行了阐述。通常意义上而言，深度优先搜索（DFS）通过递归调用堆栈比较容易实现，广义优先搜索通过队列实现。
深度优先搜索（DFS）是用于遍历或搜索图数据结构的算法，该算法从根节点开始（图搜索时可选择任意节点作为根节点）沿着每个分支进行搜索，分支搜索结束后在进行回溯。在进入下一节点之前，树的搜索尽可能的加深。
DFS的搜索算法如下（以二叉树为例）：假定根节点（图的任意节点可作为根节点）标记为,
(L) : 递归遍历左子树，并在节点结束。
(R): 递归遍历右子树，并在节点结束。
(N): 访问节点。
这些步骤可以以任意次序排列。如果（L）在（R）之前，则该过程称为从左到右的遍历；反之，则称为从右到左的遍历。根据访问次序的不同，深度优先搜索可分为 pre-order、in-order、out-order以及post-order遍历方式。
（a）检查当前节点是否为空；
（b）展示根节点或当前节点数据；
（c）递归调用pre-order函数遍历左子树；
（d）递归调用pre-order函数遍历右子树。
pre-order遍历属于拓扑排序后的遍历，父节点总是在任何子节点之前被访问。该遍历方式的图示如下：
遍历次序依次为：F -B -A-D- C-E-G- I-H.
（a）检查当前节点是否为空；
（b）递归调用in-order函数遍历左子树；
（c）展示根节点或当前节点数据；
（d）递归调用in-order函数遍历右子树。
在二叉树搜索中，in-order遍历以排序顺序访问节点数据。该遍历方式的图示如下：
遍历次序依次为：A -B - C - D - E - F - G -H-I
（a）检查当前节点是否为空；
（b）递归调用out-order函数遍历右子树；
（c）展示根节点或当前节点数据；
（d）递归调用out-order函数遍历左子树。
该遍历方式与LNR类似，但先遍历右子树后遍历左子树。仍然以图2为例，遍历次序依次为：H- I-G- F- B- E- D- C- A.
（a）检查当前节点是否为空；
（b）递归调用post-order函数遍历左子树；
（c）递归调用post-order函数遍历右子树；
（d）展示根节点或当前节点数据。
post-order遍历图示如下：
遍历次序依次为：A-C-E-D-B-H-I-G-F.
pre-order遍历方式使用场景：用于创建树或图的副本；
in-order遍历使用场景：二叉树遍历；
post-order遍历使用场景：删除树
遍历追踪也称树的序列化，是所访问根节点列表。无论是pre-order，in-order或是post-order都无法完整的描述树特性。给定含有不同元素的树结构，pre-order或post-order与in-order遍历方式结合起来使用才可以描述树的独特性。
树或图形的访问也可以按照节点所处的级别进行遍历。在每次访问下一层级节点之前，遍历所在高层级的所有节点。BFS从根节点（图的任意节点可作为根节点）出发，在移动到下一节点之前访问所有相同深度水平的相邻节点。
BFS的遍历方法图示如下：
遍历次序依次为： F-B-G-A-D-I-C-E-H.
图算法相关的R包为igraph，主要包括图的生成、图计算等一系列算法的实现。
使用方法：
参数说明：
示例：
结果展示：
DFS R输出节点排序：
使用方法：
参数含义同dfs
示例：
结果展示：
BFS R输出节点排序：
以寻找两点之间的路径为例，分别展示BFS及DFS的实现。图示例如下：
示例：
输出结果：
示例：
输出结果：
[1]维基百科： https://en.wikipedia.org/wiki/Tree_traversal
[2] GeeksforGeeks:https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
[3]http://webdocs.cs.ualberta.ca/~holte/T26/tree-traversal.html
[4]Martin Broadhurst, Graph Algorithm:http://www.martinbroadhurst.com/Graph-algorithms.html#section_1_1
[5]igraph:https://igraph.org/r/doc/dfs.html
[6]igraph:https://igraph.org/r/doc/bfs.html
[7] Depth-First Search and Breadth-First Search in Python:https://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/
相关推荐：
