图论（树的直径）

一、基础

树中最远的两个结点之间的距离被称为树的直径，连接这两点的路径被称为树的最长链（也称直径）

二、两次遍历求直径

1、从任意一个结点出发，通过bfs或者dfs对树进行一次遍历，求出与出发点距离最远的结点，记为p，这就是树的直径的一端

2、从结点p出发，通过bfs和dfs对树再进行一次遍历，求出与p距离最远的结点，记为q

3、那么p到q的路径就是树的一条直径，因为p一定是直径的一端，否则总能找到一条更长的链。在第二步遍历过程中，可以记录下来每个点第一次被访问时的前驱节点，最后从q回溯到p即可得到直径的具体方案

4、注：通过搜索不能解决负边权的问题

int to[maxn << 1], nex[maxn << 1], edge[maxn << 1], head[maxn];
int cnt, n, m, r;
ll
dis[maxn], maxd, maxv;
void add(int u, int v, int w)
{
to[++cnt] = v;
edge[cnt] = w;
nex[cnt] = head[u];
head[u] = cnt;
}
void dfs(int u, int fa)
{
if (maxd < dis[u])
{
maxd = dis[u];
maxv = u;
}
for (int i = head[u]; i; i = nex[i])
{
int v = to[i];
if (fa == v)
continue;
dis[v] = dis[u] + edge[i];
dfs(v, u);
}
}
void solve()
{
cin >> n;
for (int i = 0; i < n - 1; i++)
{
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
}
dfs(1, 0);
maxd = 0;
dis[maxv] = 0;
dfs(maxv, 0);
cout << maxd;
}

三、树形dp求直径

1、设d[x]表示从结点x出发走向以x为根的子树，能够到达的最远节点的距离，即x向下走的最长链，显然有

2、那么我们可以考虑求出经过每个点x的最长链的长度f[x]，那么整个树的直径就是最大的f[x]。对于x的任意两个结点yi，yj，经过结点x的最长链的长度由四部分组成，如下

3、当子节点枚举到i时，d[x]正好保存了从x出发向以yi为根的子树能达到的最远的结点的距离，这个距离就是，所以我们先用更新f[x]，再用更新d[x]即可

int to[maxn << 1], nex[maxn << 1], edge[maxn << 1], head[maxn];
int vis[maxn];
int cnt, n, m, r;
ll ans = 0, d[maxn];
void add(int u, int v, int w)
{
to[++cnt] = v;
edge[cnt] = w;
nex[cnt] = head[u];
head[u] = cnt;
}
void dp(int u)
{
vis[u] = 1;
for (int i = head[u]; i; i = nex[i])
{
int v = to[i];
if (vis[v])
continue;
dp(v);
ans = max(ans, d[u] + d[v] + edge[i]);
d[u] = max(d[u], d[v] + edge[i]);
}
}
void solve()
{
cin >> n;
for (int i = 0; i < n - 1; i++)
{
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
}
dp(1);
cout << ans << 'n';
}

最后

以上就是年轻胡萝卜为你收集整理的图论（树的直径）的全部内容，希望文章能够帮你解决图论（树的直径）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。