DFS求树的直径
DFS求树的直径
在算法和数据结构的学习中，树的直径求解是一个常见的问题。本文将通过一个具体的例题，详细讲解如何使用DFS（深度优先搜索）算法来求解树的直径。
前言
这个知识点我是在刷题的时候遇见的，正好也学过dfs，所以这个知识点就吸收的特别快，学这个之前记得要把dfs弄懂后再看。
一、例题引入
通过题目不难看出，这是一个树，为什么呢？大家请注意这样的一句话，题目中说同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。这句话翻译过来的意思就是一棵树，那么我们要找的就是两个点的最远距离==这棵树的直径
二、如何求树的直径呢？
树的直径有两种常用求法，分别是两次DFS以及树形DP
但后者太难理解，对于小白的我最终还是选择了前者
那么如何用两次DFS求出直径呢？
算法思路
step1：
我们随意从一个点 P 开始dfs，搜索出第一个最远的端点Q
step2：
我们从端点Q开始，搜索最远的端点W
step3：那么QW就是直径
看到这，大家可能会问 为什么？
如果按照我说的这样，那么第一次搜索出来的Q就必定是直径的某一端咯？
事实确实如此，接下来我们一起来证明一下
证明任意一点P搜出的最远端点Q必定为直径的某一端
思路证明:
我们分情况讨论
1.当随意的一点P是这条直径上的一点时
QW为直径
此时如果我们搜的最远的距离就是Q，那么这个就是直径的一个端点，那么从Q开始搜，最远的必定是W，
但是如果有一个点S才是P的最远的一个点，那么PS>PQ，
那么PS+PW>PQ+PW
那么PS+PW>QW这违背我们的前提** 我们说了QW为直径
2.当随意的一点P不是这条直径上的一点时
我们用反证法来证明
那么又会有两者情况
(1)点P与最远距离S构成的线与QW相交
如果S是最远的
那么PC+SC>PQ(因为我们一开始假设最远的应该是Q点)
那么PC+SC>PC+QC 此时两边都+CW 减去都有的PC
那么CW+SC>QC+CW
那么CW+SC>QW显然违背题意 因为一开始说了QW为直径
(2)点P与最远距离S构成的线不与QW相交
如果S是最远的
那么PS>PQ
那么PD+DS>PD+DC+CQ
那么DS>DC+CQ
那么DS+DC>2DC+CQ
那么DS+DC+CW>2DC+CQ+CW
那么WS>2DC+WQ显示违背题意 因为WQ是直径
思路总结:
证明任意一点P搜出的最远端点Q必定为直径的某一端！！！！！！
例题代码示例
#include <iostream>
#include <vector>
#include<cstring>
using namespace std;
int n, p, q, d;
bool vis[1000005]; // i节点是否走过
long long dis[100005]; // 到i节点的距离
class node
{
public:
int id, st; // 到此节点的距离
};
vector<node> h[100005];
void dfs(int t)
{
// 搜寻这个节点能到达的所有节点
for (int i = 0; i < h[t].size(); i++)
{
int tt = h[t][i].id;
if (!vis[tt])
{
vis[tt] = 1;
dis[tt] = dis[t] + h[t][i].st;
dfs(tt);
}
}
}
int main()
{
cin >> n;
for (int i = 1; i < n; i++)
{
cin >> p >> q >> d;
h[p].push_back({q, d});//p节点可以到q节点 那么q节点也可以到p节点
h[q].push_back({p, d});//所以互相都要包含进去
}
//随意从一个点出发 这里我们就从1节点出发就行
//此时dis[1]为0 记得要初始化 这里我们dis是全局变量 所以一开始是0
dfs(1); // 当前在第一个节点
int Q;//直径的一个端点
long long maxx = -1;
for (int i = 1; i <= n;i++)
{
if(dis[i]>maxx)
{
maxx = max(maxx, dis[i]);
Q = i;//找到其中一个端点是哪个节点
}
}
//找完Q端点后 继续找另一端的端点
//记得初始化
memset(dis, 0, sizeof(dis));
memset(vis, 0, sizeof(vis));
vis[Q] = 1;
dfs(Q);
int P;//直径的另一端
maxx = -1;
for (int i = 1; i <= n; i++)
{
if (dis[i] > maxx)
{
maxx = max(maxx, dis[i]);
P = i;//另一端的端点
}
}
//此时maxx为直径
cout << ((11 + (maxx + 10)) * maxx) / 2;
return 0;
}
同样的题目还有洛谷P3304