深度优先搜索

将搜索看成一张图，搜索都与图有关

图的储存方式：邻接表和邻接矩阵，搜索很多时候，大多用邻接表

回忆

树于图的深度优先遍历

有两个过程：向下搜索与向上回溯。

重点：标记

void dfs(int u){
  vis[u]=1;//标记（时间戳）
  for(int i=h[u];i!=-1;i=ne[i]){
    int t=e[i];
    if(vis[t]){
      continue;
    }
    dfs(t);
  }
  return ;
}

时间：$O(n+m)$

树与图的DFS序

上面的加强版，记录搜到的点的顺序

进入递归的点以及即将回溯的点，其长度为$2N$

这样每个数字都会出现两次，称为$l,r$。

可以将树变成线段（方便找子树，变成序列统计问题）

void dfs(int u){
  vis[u]=1;
  st[++cnt]=u;
  for(int i=h[u];i!=-1;i=ne[i]){
    int t=e[i];
    if(vis[t]){
      continue;
    }
    dfs(t);
  }
  st[++cnt]=u;
  return ;
}

树的深度

直接求出此节点与根节点的直线距离

void dfs(int u){
  vis[u]=1;
  for(int i=h[u];i!=-1;i=ne[i]){
    int t=e[i];
    if(vis[t]){
      continue;
    }
    d[t]=d[u]+1;
    dfs(t);
  }
}

树的重心

看讲义（自下往上）

连通块划分

看一下还有几个未遍历到。

广度优先遍历

void bfs(){
  q.push(1);
  dist[1]=1;
  while(q.size()){
    int x=q.front();
    q.pop();
    for(int i=h[x];i!=-1;i=ne[i]){
      int y=e[i];
      if(dst[y]){
        continue;
      }
      dist[y]=dist[x]+1;
      q.push(y);
    }
  }
}

特点：队列里的元素只会包含本层和上一层的，有二分性，有单调性

拓扑排序

对有向无环图有，否则无，线性排序

每次找到入读为0的点加入。

搜索

剪枝

爆搜剪枝

优化搜索顺序

排除亢余剪枝

可行性剪枝

最优性剪枝

迭代加声

迭代加深就是$DFS$的一种特定优化

_思考方式重要_

题目要求较高

_多少步没搜到就无解_!

实现过程

1. 前提：搜索较浅（不然会超时）

从深度1开始，将限制逐渐加升到$n$。每次就重新搜！！

具体过程

1. 先搜索深度为dep的所有节点，$dep$初始为一。
2. 如果到了深度，直接回根，dep++

时间复杂度

时间复杂度不高！！

由于在树的浅层，所以搜索的节点不多，基本时间为$O(最后一层节点数)$

例题

加成序列

思路

本题n的范围不大，是一道迭代加深的典型题目，这序列各个方案组合后相当于一棵树

爆搜：枚举每个项的数字。

时间复杂度：$O(n^n)$

优化：

1. 优化搜索顺序：为了让数字个数越少，可以枚举位置，数字从大到小

代码

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,path[N];
bool dfs(int u,int dep){
	if(u==dep){
		return path[u-1]==n;
	}
	bool st[N]={0};
	for(int i=u-1;i>=0;i--){
		for(int j=i;j>=0;j--){
			int s=path[i]+path[j];
			if(s>n||s<=path[u-1]||st[s]){
				continue;
			}
			st[s]=1;
			path[u]=s;
			if(dfs(u+1,dep)){
				return 1;
			}
		}
	}
}
int main(){
	path[0]=1;
	while(cin>>n&&n){
		int dep=1;
		while(!dfs(1,dep)){
			dep++;
		}
		for(int i=1;i<=dep;i++){
			cout<<path[i]<<" ";
		}
		cout<<endl;
	}
	return 0;
} 

双向深搜

某棵树比较深，为了避免在深层次的子树上浪费时间，我们可以注意题目是否提供初态和终态

选择是否用双向搜索 过程：从初态到终态出发各搜索一半，得到答案