时间戳

首页 > 解决方案 > 树形图的直径

c++ - 树形图的直径

问题描述

我在问自己查找树直径的代码有什么问题：

（通过树的直径，我的意思是该树图中两个节点之间的最大距离）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 1000005
int n,a,b;
int dist[MAXN];
vector<int> adj[MAXN];
vector<int> ways;
void dfs(int U, int father){
    if(father==U){
        dist[U]=1;
    }
    else{
        dist[U]=1+dist[father];
    }
    for(int i=0;i<(int)adj[U].size();i++){
        int V=adj[U][i];
        if(dist[V]==-1) dfs(V,U);
    }
}
void solve(int S){
    dist[S]=0;
    for(int j=0;j<(int)adj[S].size();j++){
        int w=adj[S][j];
        dfs(w,w);
        int maxdist=0;
        for(int i=1;i<=n;i++){
            if(dist[i]!=-1){
                maxdist=max(maxdist,dist[i]);
                dist[i]=0;
            }
        }
        ways.push_back(-maxdist);
    }
}
int main(){
    cin>>n;
    if(n==2) cout<<"1\n";
    else{
    for(int i=1;i<=n;i++){
      dist[i]=-1;
    }
    for(int i=1;i<n;i++){
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int vert;
    for(int i=1;i<=n;i++){
        if((int)adj[i].size()>1){
            vert=i;
            break;
        }
    }
    solve(vert);
    sort(ways.begin(),ways.end());
    int ret=-(ways[0]+ways[1]);
    cout<<ret<<"\n";
    }
    return 0;
}

对我来说，这听起来合乎逻辑且非常程序化，但我将其提交给在线法官并没有被接受。这是怎么回事？

标签： c++graphtree

解决方案

您可以通过 A 和 B 测量树中两个节点之间的距离。

distanceBetwwen_A_and_B = Distance A -> CommonAncestor(A, B)
                        + Distance B -> CommonAncestor(A, B);

因此，对于给定的祖先节点 G，它的最大半径为：

Diameter(G)   = Distance_To_Furthest_Child(G->left)
              + Distance_To_Furthest_Child(G->right)

但是它的一个后代可能有比它自己更大的半径。

Max_Diameter(G) = max(Diameter(G), Max_Diameter(G->left), Max_Diameter(G->right))

由此，您应该能够进行深度优先搜索和单次遍历来计算 Max_Diameter(Root)

struct Node
{
    Node*  l;
    Node*  r;
    int    maxD;
};

int findMaxD(Node* root)
{
    if (root == nullptr) {
        return 0;
    }
    calcMaxDiameter(root);
    return root->maxD;
}
/*
 * Sets the maxD value of a node
 * Returns the distance to the furthest decendant
 */
int calcMaxDiameter(Node* root)
{
    // If we fall of the end
    // The distance is zero.
    if (root == nullptr) {
        return 0;
    }
    int l_Distance = calcMaxDiameter(root->l);
    int r_Distance = calcMaxDiameter(root->r);

    // Calculate the preliminary Radius.
    root->maxD = l_Distance + r_Distance;
    if (root->l) {
        // If there is a left node see if it is bigger
        // than the current radius
        root->maxD = std::max(root->maxD, root->l->maxD);
    }
    if (root->r) {
        // If there is a right node....
        root->maxD = std::max(root->maxD, root->r->maxD);
    }
    // Return the distance to the furthest
    // ancestor. Add one for the distance from here
    // to the parent.
    return std::max(l_Distance, r_Distance) + 1;
}

推荐阅读