图论—树的直径（树形DP、BFS）

本文主要是介绍图论—树的直径（树形DP、BFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$树的直径——树形DP、两次BFS$

不再详细解释代码，只记录完整模板。

树形DP

可以计算负权边。

时间复杂度：$O(n)$。

设$D[x]$表示从节点$x$出发走向以$x$为根的字数，能够到达的最远节点的距离；设$y_i$表示子节点，$edge(x,y)$表示边权，则有：

$D[x]=ma{x}_{1\le i\le t}(D[y_i]+edge(x_i,y_i))$

设F[x]为经过节点x的最长链长度，则有：

$F[x]=ma{x}_{1\le j<i\le t}(D[y_i]+D[y_j]+edge(x,y_i)+edge(x,y_j))$

int res, n, b[N], d[N];
vector<PII> a[N];
void dp(int x) {b[x] = 1;for(int i = 0; i < a[x].size(); i ++ ) {int t = a[x][i].fi, u = a[x][i].se;if(b[t]) continue;dp(t);res = max(res, d[x] + d[t] + u);d[x] = max(d[x], d[t] + u);}
}void Solved() {cin >> n;for (int i = 0; i < n - 1; ++i) {int x, y, z; cin >> x >> y >> z;a[x - 1].push_back({y - 1, z});a[y - 1].push_back({x - 1, z});}dp(0);	cout << res << endl;
}

两次BFS

实现最长直径长度，计算出直径上的具体节点。

无法计算负权边！！！

时间复杂度：$O(n)$。

struct Node {int id, distance;};// 结点
struct Edge {int to, weight;};  // 边vector<vector<Edge>> tree; //用于存储树的结构
vector<bool> visited;      //标记
vector<int> parent;        //存放父节点Node bfs(int start) {// 第一次 BFS，从任意结点开始找到最远的结点queue<Node> q;visited.assign(tree.size(), false);q.push({start, 0});visited[start] = true;Node farthest = {start, 0};while (!q.empty()) {Node current = q.front(); q.pop();if (current.distance > farthest.distance) farthest = current;for (const Edge& edge : tree[current.id]) {if (!visited[edge.to]) {visited[edge.to] = true;q.push({edge.to, current.distance + edge.weight});parent[edge.to] = current.id; // 保存父节点信息}}}return farthest;
}vector<int> diameter() {// 第二次 BFS，从最远的结点开始找到直径的另一端Node start = bfs(0);Node end = bfs(start.id);vector<int> path;path.push_back(end.id);// 从 end.id 向上回溯到 start.id，得到直径上的所有节点int current = end.id;while (current != start.id) {current = parent[current]; // 根据父节点数组回溯path.push_back(current);}reverse(path.begin(), path.end());path.push_back(end.distance);   //将最长直径一并返回return path;
}int main() {int n; cin >> n;tree.resize(n); parent.resize(n, -1);for (int i = 0; i < n - 1; ++i) {int x, y, z; cin >> x >> y >> z;tree[x - 1].push_back({y - 1, z});tree[y - 1].push_back({x - 1, z});}vector<int> path = diameter();cout << path.back() << endl;    //输出最长直径path.pop_back();                //将答案删除for (int node : path)         //输出最长直径具体节点cout << node + 1 << " ";return 0;
}

这篇关于图论—树的直径（树形DP、BFS）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---