当前位置 博文首页 > 学渣日记：两种方法求树的直径（BFS/DFS)
树的直径：树上距离最远的两个点的距离。
方法：
随机选择一个节点，假设是1，在以1为根的有根树上进行一遍dfs或者bfs遍历，并记录下每个点到根的距离。
选择到根距离最远的点u（如果有多个，随机选择一个都可以），根据节点u再建立一个有根树，这个时候以u为根的有根树上进行一遍dfs或者bfs遍历，并记录下每个点到根的距离。
第二次遍历之后，距离最远的点对应的距离就是树的直径。
代码：
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int n, u, v;
vector<int> map[1111111];
int book[1111111];
int dis[1111111], tmax, des;
/*
//根的前一个结点是-1
void dfs(int pre, int cur) {
book[cur] = 1;
if (pre != -1) {
sum++;
//tmax：最大距离，des：最远的点
if (tmax < sum) {
tmax = sum;
des = cur;
}
}
for (auto i:map[cur]) {
if (book[i] != 1) {
dfs(cur, i);
}
}
//取消标记，回溯
book[cur] = 0;
if (pre != -1)
sum--;
}
*/
//求最长路径还是bfs更简单
void bfs(int root) {
memset(book, 0, sizeof(book));
memset(dis, 0, sizeof(dis));
queue<int> q;
book[root] = 1;
q.push(root);
while (q.size()) {
int t = q.front();
q.pop();
if (dis[t] > tmax) {
tmax = dis[t];
des = t;
}
for (auto i : map[t]) {
if (!book[i]) {
book[i] = 1;
q.push(i);
dis[i] = dis[t] + 1;
}
}
}
}
int main() {
cin >> n;
if(!n){
cout<<0;
return 0;
}
n--;
while (n--) {
cin >> u >> v;
map[u].push_back(v);
map[v].push_back(u);
}
bfs(1);
bfs(des);
cout << tmax;
return 0;
}
