1. DFS
数据结构：stack
空间复杂度：O(h)
不具最短性
每个DFS都对应一个搜索树
2. BFS
数据结构：queue
空间复杂度：O(2^h)
最短路
一般思路
queue <-初始
while(队列不空)
{
t<-队头
拓展队头
}
练习题
3. 树与图的深度优先遍历
模板代码
vector<int> v[N];
int n, m;
bool st[N];
// 以u为根的子树中点的数量
void dfs(int u) {
st[u] = 1; // 标记一下，已经被搜过了
int sum = 1, res = 0; // sum是当前子树大小，res是删掉当前点每一个连通块大小的最大值
for (int i = 0; i < v[u].size(); i ++ ) { // 遍历u的出边
int k = v[u][i]; // 编号
if (!st[k]) {
// 具体思路
}
}
}
int main() {
cin >> n;
for (int i = 0; i < n - 1; i ++ ) {
int a, b;
cin >> a >> b;
v[b].push_back(a), v[a].push_back(b); // 存图，具体情况具体分析
}
dfs(1);
return 0;
}
