DFS与BFS在算法中的应用
DFS与BFS的一些性质拓展出了许多算法的处理。
树的欧拉序
这玩意在树上DP中常见（用）。
欧拉序是从根节点遍历一棵树，在遍历中做三件事：
记录下当前节点
遍历儿子节点
再次记录下当前节点
第一次记录可以视为入栈时间，第二次记录可以视为出栈时间。
伪代码：
PROC DFS(x);
begin
Push(x);
DFS(son);
Push(x);//有必要时记录一下是入栈还是出栈
end;
代码如下：
type
Rec=record
x,next:longint;//树边
end;
inf=record
x:longint;
ifdo:boolean;//ifdo为true表示当前位入栈，否则为出栈
end;
var
Tree,V:array[1..10000] of longint;
Etree:array[1..10000] of Rec;
DFSArr:array[1..20000] of inf;
n,i,w,root,top:longint;
procedure ins(f,s:longint);//插入边
begin
inc(top);
Etree[top].x:=s;
Etree[top].next:=Tree[f];
Tree[f]:=top;
end;
procedure DFS(x:longint);//求欧拉序
var
v:longint;
begin
inc(top);
DFSArr[top].x:=x;
DFSArr[top].ifdo:=true;
v:=Tree[x];
while v<>0 do
begin
DFS(Etree[v].x);
v:=Etree[v].next;
end;
inc(top);
DFSArr[top].x:=x;
end;
procedure Print;//输出欧拉序
var
vi:longint;
begin
for vi:=1 to top do
begin
if DFSArr[vi].ifdo then write('in ')
else write('out ');
writeln(DFSArr[vi].x)
end;
end;
begin
read(n);//读入
for i:=1 to n do
begin
read(w);//w为其父亲，若w为0则表示此为根节点
if w<>0 then ins(w,i)//建边
else root:=i;
end;
top:=0;
DFS(root);//求欧拉序
Print;//输出
end.
例如ST算法求LCA。将欧拉序求出来之后，两点u与v的LCA相当于u入栈时间到v出栈时间内记录的区间内深度最小的节点。所以配上RMQ即可求解。
还有一些应用。例如将入栈时放入的点，点权值记为+1，出栈时记为-1。那么 根到一个点的路径长度 就是 点入栈时记录的点 权值的前缀和。
图的DFS序
话说内容差不多。只不过每一个点只会被记录一次。
树上一棵子树，可以对应其DFS序上的一段区间。
图的DFS生成树
我们按照DFS的顺序来拓展节点。这样会得到一些树边（可以组成生成树），以及一些不是树边的边。
图的DFS生成树有一个重要性质：除了树边，只会存在前向边或后向边，不存在跨子树的边。
例如Tarjan求强连通分量的算法，就是如果找到了一条后向边（指向祖先），那么这一块都可以视为一个强连通分量（当然具体算法还有一些补充）。
求欧拉回路与欧拉路径
欧拉回路是指一个点不重复也不遗漏地跑完所有边，再回到原来的点的一条路径（点可以重复）。
欧拉路径是指一个点不重复也不遗漏地跑完所有边，不回到原来的点的一条路径（点可以重复）。
欧拉图是指任何一个点都可以跑一个欧拉回路的图。
半欧拉图是指从一个起点跑到终点，可以跑出一条欧拉路径的图。
对于一张欧拉图，求一个欧拉回路只需要从任何一个节点开始跑DFS，对于每一条边，先拓展其他节点，拓展完之后再把这条边记录下来。
最后记录的逆序即为一个欧拉回路。
伪代码：
PROC DFS(x);
begin
enumerate(e)
begin
DFS(e.x);
Push(e);//注意这里是记录边
end;
end;
记录的逆序为欧拉回路。
而对于一个半欧拉图，我们就把起点和终点建一条边，之后跑一个欧拉回路，再删去建的那条边就可以求出欧拉路径了。