一棵树的树根可以提供最小的高度-yiteyi-C++库

给定一个具有树特征的无向图。可以选择任何节点作为根，任务是只找到那些使树的高度最小化的节点。

null

例子： 在下面的图表中，所有的节点都是一个接一个的根，我们可以看到当3和4是根时，树的高度是最小的（2），所以{3，4}是我们的答案。

图片[1]-一棵树的树根可以提供最小的高度-yiteyi-C++库

我们可以通过首先考虑一维解来解决这个问题，即如果给定了最长的图，那么当总节点数为奇数时，将使高度最小化的节点将是中间节点，如果总节点数为偶数，则将是中间两个节点。这个解决方案可以通过以下方法实现——从路径两端开始两个指针，每次移动一步，直到指针相交或相隔一步，在端点处，指针将位于那些将使高度最小化的节点，因为我们已将节点均匀分开，所以高度将最小。同样的方法也适用于一般树。从所有叶节点开始指针，每次向内移动一步，继续合并移动时重叠的指针，最后只有一个指针留在某个顶点上，或者两个指针保持一段距离。这些节点代表顶点的根，这将最小化树的高度。所以我们可以只有一个根，或者最多两个根作为最小高度，这取决于树的结构，如上所述。对于实现，我们将不使用实际指针，而是遵循类似BFS的方法，首先将所有叶节点推入队列，然后将它们从树中移除，然后将下一个新叶节点推入队列，这个过程将继续进行，直到我们的树中只有1或2个节点，这代表了结果。

C++

                         //  C++ program to find root which gives minimum height to tree                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // This class represents a undirected graph using adjacency list                       
                         // representation                       
                         class                                     Graph                       
                         {                       
                         public                                     :                       
                                                 int                                     V;                                     // No. of vertices                       
           
                                                 // Pointer to an array containing adjacency lists                       
                                                 list<                                     int                                     > *adj;                       
           
                                                 // Vector which stores degree of all vertices                       
                                                 vector<                                     int                                     > degree;                       
           
                                                 Graph(                                     int                                     V);                                     // Constructor                       
                                                 void                                     addEdge(                                     int                                     v,                                     int                                     w);                                     // To add an edge                       
           
                                                 // function to get roots which give minimum height                       
                                                 vector<                                     int                                     > rootForMinimumHeight();                       
                         };                       
           
                         // Constructor of graph, initializes adjacency list and                       
                         // degree vector                       
                         Graph::Graph(                                     int                                     V)                       
                         {                       
                                                 this                                     ->V = V;                       
                                                 adj =                                     new                                     list<                                     int                                     >[V];                       
                                                 for                                     (                                     int                                     i = 0; i < V; i++)                       
                                                 degree.push_back(0);                       
                         }                       
           
                         // addEdge method adds vertex to adjacency list and increases                       
                         // degree by 1                       
                         void                                     Graph::addEdge(                                     int                                     v,                                     int                                     w)                       
                         {                       
                                                 adj[v].push_back(w);                                     // Add w to v’s list                       
                                                 adj[w].push_back(v);                                     // Add v to w’s list                       
                                                 degree[v]++;                                     // increment degree of v by 1                       
                                                 degree[w]++;                                     // increment degree of w by 1                       
                         }                       
           
                         //  Method to return roots which gives minimum height to tree                       
                         vector<                                     int                                     > Graph::rootForMinimumHeight()                       
                         {                       
                                                 queue<                                     int                                     > q;                       
           
                                                 //  first enqueue all leaf nodes in queue                       
                                                 for                                     (                                     int                                     i = 0; i < V; i++)                       
                                                 if                                     (degree[i] == 1)                       
                                                 q.push(i);                       
           
                                                 //  loop until total vertex remains less than 2                       
                                                 while                                     (V > 2)                       
                                                 {                       
                                                 int                                     popEle = q.size();                       
                                                 V -= popEle;                                     // popEle number of vertices will be popped                       
                                   
                                                 for                                     (                                     int                                     i = 0; i < popEle; i++)                       
                                                 {                       
                                                 int                                     t = q.front();                       
                                                 q.pop();                       
           
                                                 // for each neighbour, decrease its degree and                       
                                                 // if it become leaf, insert into queue                       
                                                 for                                     (                                     auto                                     j = adj[t].begin(); j != adj[t].end(); j++)                       
                                                 {                       
                                                 degree[*j]--;                       
                                                 if                                     (degree[*j] == 1)                       
                                                 q.push(*j);                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 //  copying the result from queue to result vector                       
                                                 vector<                                     int                                     > res;                       
                                                 while                                     (!q.empty())                       
                                                 {                       
                                                 res.push_back(q.front());                       
                                                 q.pop();                       
                                                 }                       
                                                 return                                     res;                       
                         }                       
           
           
                         //  Driver code                       
                         int                                     main()                       
                         {                       
                                                 Graph g(6);                       
                                                 g.addEdge(0, 3);                       
                                                 g.addEdge(1, 3);                       
                                                 g.addEdge(2, 3);                       
                                                 g.addEdge(4, 3);                       
                                                 g.addEdge(5, 4);                       
           
                                                 // Function Call                       
                                                 vector<                                     int                                     > res = g.rootForMinimumHeight();                       
                                                 for                                     (                                     int                                     i = 0; i < res.size(); i++)                       
                                                 cout << res[i] <<                                     " "                                     ;                       
                                                 cout << endl;                       
                         }                       

Python3

                         # Python program to find root which gives minimum                       
                         # height to tree                       
           
                         # This class represents a undirected graph using                       
                         # adjacency list representation                       
           
           
                         class                                     Graph:                       
           
                                                 # Constructor of graph, initialize adjacency list                       
                                                 # and degree vector                       
                                                 def                                     __init__(                                     self                                     , V, addEdge, rootForMinimumHeight):                       
                                                 self                                     .V                                     =                                     V                       
                                                 self                                     .adj                                     =                                     dict                                     ((i, [])                                     for                                     i                                     in                                     range                                     (V))                       
                                                 self                                     .degree                                     =                                     list                                     ()                       
                                                 for                                     i                                     in                                     range                                     (V):                       
                                                 self                                     .degree.append(                                     0                                     )                       
           
                                                 # The below lines allows us define methods outside                       
                                                 # of class definition                       
                                                 # Check                           http://bit.ly/2e5HfrW                          for better explanation                       
                                                 Graph.addEdge                                     =                                     addEdge                       
                                                 Graph.rootForMinimumHeight                                     =                                     rootForMinimumHeight                       
           
           
                         # addEdge method adds vertex to adjacency list and                       
                         # increases degree by 1                       
                         def                                     addEdge(                                     self                                     , v, w):                       
                                                 self                                     .adj[v].append(w)                                     # Adds w to v's list                       
                                                 self                                     .adj[w].append(v)                                     # Adds v to w's list                       
                                                 self                                     .degree[v]                                     +                                     =                                     1                                     # increment degree of v by 1                       
                                                 self                                     .degree[w]                                     +                                     =                                     1                                     # increment degree of w by 1                       
           
           
                         # Method to return roots which gives minimum height to tree                       
                         def                                     rootForMinimumHeight(                                     self                                     ):                       
           
                                                 from                                     queue                                     import                                     Queue                       
                                                 q                                     =                                     Queue()                       
           
                                                 # First enqueue all leaf nodes in queue                       
                                                 for                                     i                                     in                                     range                                     (                                     self                                     .V):                       
                                                 if                                     self                                     .degree[i]                                     =                                     =                                     1                                     :                       
                                                 q.put(i)                       
           
                                                 # loop until total vertex remains less than 2                       
                                                 while                                     (                                     self                                     .V >                                     2                                     ):                       
                                                 p                                     =                                     q.qsize()                       
                                                 self                                     .V                                     -                                     =                                     p                       
                                                 for                                     i                                     in                                     range                                     (p):                       
                                                 t                                     =                                     q.get()                       
           
                                                 # for each neighbour, decrease its degree and                       
                                                 # if it become leaf, insert into queue                       
                                                 for                                     j                                     in                                     self                                     .adj[t]:                       
                                                 self                                     .degree[j]                                     -                                     =                                     1                       
                                                 if                                     self                                     .degree[j]                                     =                                     =                                     1                                     :                       
                                                 q.put(j)                       
           
                                                 #  Copying the result from queue to result vector                       
                                                 res                                     =                                     list                                     ()                       
                                                 while                                     (q.qsize() >                                     0                                     ):                       
                                                 res.append(q.get())                       
           
                                                 return                                     res                       
           
           
                         # Driver code                       
                         g                                     =                                     Graph(                                     6                                     , addEdge, rootForMinimumHeight)                       
                         g.addEdge(                                     0                                     ,                                     3                                     )                       
                         g.addEdge(                                     1                                     ,                                     3                                     )                       
                         g.addEdge(                                     2                                     ,                                     3                                     )                       
                         g.addEdge(                                     4                                     ,                                     3                                     )                       
                         g.addEdge(                                     5                                     ,                                     4                                     )                       
           
                         # Function call                       
                         res                                     =                                     g.rootForMinimumHeight()                       
                         for                                     i                                     in                                     res:                       
                                                 print                                     (i,end                                     =                                     " "                                     )                       
           
                         # This code is contributed by Nikhil Kumar Singh(nickzuck_007)                       

输出

3 4

当我们访问每个节点一次时 时间复杂性 解的形式是O（n）。

本文由 乌特卡什·特里维迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章