树的直径即为一棵树中距离最远的两点之间的路径
方法一:DFS
先以任意一点为起点跑一遍dfs,记录离起点距离最远的点p(这个点一定是直径的一个端点,感性理解一下不证明了),然后再以最远点再跑一遍dfs,记录此时距离最远的点q,那么pq就是该树的直接
树中有负权边时不可以用这个方法文章来源:https://www.toymoban.com/news/detail-808569.html
const int N = 10000 + 10;
int n, c, d[N];
vector<int> g[N];
void dfs(int u, int fa)
{
for (int v : E[u])
{
if (v == fa) continue;
d[v] = d[u] + 1; // 如边有权值,把1换成权值即可
if (d[v] > d[c]) c = v; // 更新最大距离的点
dfs(v, u);
}
}
int main()
{
cin >> n;
for (int i = 1; i < n; i++)
{
int u, v;
scanf("%d %d", &u, &v);
g[u].push_back(v), g[v].push_back(u);
}
dfs(1, 0); // 第一遍dfs
int p = c; // 一个端点
d[c] = 0;
dfs(c, 0); // 第二遍dfs
int q = c; // 另一个端点
cout << d[c];
return 0;
}
方法二:树形dp
dp[u]
为以u为根的子树中离u最远的点的路径长度
转移方程(v为u的子结点):dp[u] = max(dp[u], dp[v] + w(u, v))
两条经过根结点的最长路径即为该子树中的直径
转移方程:zj = max(zj, dp[u] + dp[v] + w(u, v))
文章来源地址https://www.toymoban.com/news/detail-808569.html
const int N = 10000 + 10;
int n, zj = 0;
int dp[N];
vector<int> g[N];
void dfs(int u, int fa)
{
for (int v : E[u])
{
if (v == fa) continue;
dfs(v, u);
zj = max(zj, dp[u] + dp[v] + 1); // 如为有权边,把1换成权值即可
dp[u] = max(dp[u], dp[v] + 1); // 如为有权边,把1换成权值即可
}
}
int main()
{
cin >> n;
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
g[u].push_back(v), g[v].push_back(u);
}
dfs(1, 0);
cout << zj << '\n';
return 0;
}
到了这里,关于【图论】树的直径的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!