今天学习搜索与回溯
特点
每次深度优先搜索的结果必然是图的一个连通分量。深度优先搜索可以从多点发起。如果将每个节点在深度优先搜索过程中的"结束时间"排序(具体做法是创建一个list,然后在每个节点的相邻节点都已被访问的情况下，将该节点加入list结尾，然后逆转整个链表),则我们可以得到所谓的"拓扑排序"，即topological sort.
当然,当人们刚刚掌握深度优先搜索的时候常常用它来走迷宫。事实上我们还有别的方法，那就是广度优先搜索 (BFS)。状态(state):状态是指问题求解过程中每一步的状况。
算符(operator)算符是把问题从一种状态变换到另一种状态的方法代号。算符的取值范围就是搜索的范围。(一般设为局部变量)。
节点(node):用来表明状态特征及相关信息。
效率
作为搜索算法的一种，DFS对于寻找一个解的NP(包括NPC)问题作用很大。但是，搜索算法毕竟是时间复杂度是O(n!)的阶乘级算法，它的效率非常低，在数据规模变大时，这种算法就显得力不从心了。
关于深度优先搜索的效率问题，有多种解决方法。最具有通用性的是剪枝(prunning)，也就是去除没有用的搜索分支。有可行性剪枝和最优性剪枝两种。此外，对于很多问题，可以把搜索与动态规划(DP,dynamic programming)、完备匹配(匈牙利算法)等高效算法结合。
剩余内容，见网站
https://upimg.baike.so.com/doc/4988346-5211910.html