深度优先搜索dfs

快6月份了，一学年就又这么荒废了。记录一下dfs。

1、栈

首先了解一下栈吧，dfs本质是递归，也就是栈的调用。

1、栈的特点：与队列不同，他是先进后出。

2、栈的基本操作：

1、头文件：#include<stack>

2、stack<int> st;

方法：

st.empty()：判断是否为空

st.size()：判断元素个数

st.top()：返回栈顶元素

st.pop()：删除栈顶元素

st.push()：进栈

ps：栈没有迭代器，不可遍历

2、dfs

1、通俗理解：即一条路走到黑的搜索方式，走到黑了那么就返回上一个节点继续走，直到满足要求。

2、最easy的模板：

把大佬举的栗子搬过来用：

全排列：

例如n=3，则有6种方案：1 2 3,1 3 2,2 1 3,2 3 1,3 1 2,3 2 1。

由高中数学排列组合的知识可知，全排列就相当于把n个不同的人安排在n个不同的座位上的方法数。

假设我们每次都是按从第一个座位到最后一个座位的顺序安排人，那么第一个座位可以安排的人有1到n，当第一个座位安排了第i个人时，则第二个座位只能从剩下的人里安排，以此类推。

递归的来想这个问题：如果第一个位置确定安排某个人以后，相当于在剩下的位置上对未安排的人求全排列，也就是对原问题的子问题求解。

我们可以把每个座位安排的不同的人当作一个分支，把下一次要选的座位当作一个树的节点，那么可以得到一棵树。所有座位都安排了人——即达到树的最大深度时，就是一种方案。

我们仍然以n=3为例。

void DFS(i，前i-1个座位上安排的人的编号)
{//当前在给第i个座位安排人，谁被安排过可以通过全局的标记数组判断
If(i>n) 输出，返回;
else
	for(i=1到n)
	{
		if(i没有安排过)
		安排i到该座位上，标记i已被用过,DFS(i+1,前i个座位上安排的人的编号),将i从座位上取下，撤销标记;
		}
}//递归的过程是不是很像栈的使用过程，事实上函数的递归就是通过栈来完成的

用dfs求以某点开始的无向树的最大路径：

ps:若求树的最大路径，则两遍dfs即可。

void dfs(int dep,int u,int pre) {  
    if(dep>maxDep) {//如果该路径的长度大于maxDep，更新maxDep和最长路的端点  
        maxDep=dep;  
        nd=u;  
    }  
    int i=h[u];  
    while(i) {  
        if(node[i].e!=pre)//因为是树，所以只用判断当前节点的前一个节点是否与其下一个节点相同  
            dfs(dep+1,node[i].e,u);  
        i=node[i].nxt;  
    }  
}