现在的位置: 首页 > 综合 > 正文

GOOGLE的一道笔试题—求给定连通无环无向图可以生成的最小高度树

2018年05月02日 ⁄ 综合 ⁄ 共 4261字 ⁄ 字号 小 中 大 ⁄ 评论关闭

最近看到一道谷歌笔试题，“已知一颗无向无环连通图T的所有顶点和边的信息，
现需要将其转换为一棵树，要求树的深度最小，请设计一个算法找到所有满足要
求的树的根结点，并分析时空复杂度（描述算法即可，无需代码）”

其实就是给定一个无向连通图，求以哪些顶点为根可以得到深度最小的树，思路比较简单，
主要有两个步骤：
（1）首先选取1号结点作为树根，进行一遍DFS，在DFS时计算每个节点的countv值，表示
以当前节点作为树根的子树的最大深度+1
（2）进行第二遍DFS，进行DP，对于结点i的每个邻接点j，maxDepth(i, j)表示以i为根连同j表示的子树
    所构成的子树的最大深度，那么
        maxDepth(i, j) = countv[j],  当j尚未被访问
                         max(maxDepth(j, k)) + 1, k为j的邻居节点且k!=i, 当j被访问过
    上述公式画个图就很容易理解了，当j尚未被访问时期是就是使用了（1）中的计算结果，否则就是使用DP利用
    邻居的当前状态来计算自己的状态

  最后答案就是：min(max(maxDepth(i, j), for all i's neighbour j)), for all nodes i

  (1)的时间复杂度是O(V + E), (2) 的时间复杂度是O(V * E), 所以总体时间复杂度是O(V * E)
*/

[c-sharp] view
plaincopy

  1. #include <iostream>  
  2. #define MAX_N 100  
  3. using namespace std;  
  4. struct head //邻接表  
  5. {  
  6.     int toId;      //边的to结点的id             
  7.     int maxDepth;  //表示以i为树根，连通j所带子树的最大深度  
  8.     head *next;  
  9.     head()  
  10.     {  
  11.         toId = maxDepth = 0;  
  12.         next = NULL;  
  13.     }  
  14. }*heads[MAX_N];  
  15. int countv[MAX_N];                //第一遍DFS时记录以当前节点作为子树的最大深度+1  
  16. int res[MAX_N], num, minDepthVal; //记录最终结果，具有最小最大度数minDepthVal的结点个数num以及分别是哪些结点  
  17. bool v[MAX_N]; //标记结点是否被访问了  
  18. int nodeN;     //结点个数  
  19. //初始化  
  20. void init()  
  21. {  
  22.     for(int i = 0; i < MAX_N; i++)  
  23.     {  
  24.         countv[i] = res[i] = 0;  
  25.         v[i] = false;  
  26.         head *curPtr = heads[i];  
  27.         while(curPtr != NULL)  
  28.         {  
  29.             head *tempPtr = curPtr->next;  
  30.             delete curPtr;  
  31.             curPtr = tempPtr;  
  32.         }  
  33.         heads[i] = NULL;  
  34.     }  
  35. }  
  36. //向临街表中插入一条边  
  37. void insertEdge(int from, int to)  
  38. {  
  39.     head *newHead = new head();  
  40.     newHead->toId = to;  
  41.     newHead->next = heads[from];  
  42.     heads[from] = newHead;  
  43. }  
  44. //第一遍DFS计算Account  
  45. int getAccount(int id)  
  46. {  
  47.     //标记访问  
  48.     v[id] = true;  
  49.     //最大深度+1的初始值为1  
  50.     int maxD = 1;  
  51.     //遍历当前结点的临街表  
  52.     head *curPtr = heads[id];  
  53.     while(curPtr)  
  54.     {  
  55.         //邻接点id  
  56.         int toId = curPtr->toId;  
  57.         curPtr = curPtr->next;  
  58.         if(v[toId]) continue;  
  59.         int tempD = getAccount(toId);  
  60.         //更新最大深度+1的值  
  61.         if(tempD + 1 > maxD) maxD = tempD + 1;  
  62.     }  
  63.     //记录结果  
  64.     return countv[id] = maxD;  
  65. }  
  66. //第二遍DPF计算以每个结点为根得到的树的最大深度  
  67. void getAnswer(int id)  
  68. {  
  69.     //如果访问过就不再访问  
  70.     if(v[id]) return;  
  71.     //标记未访问结点为访问状态  
  72.     v[id] = true;  
  73.     head *curPtr = heads[id];  
  74.     //孤立点的最大深度是0，所以maxD的初始值为0  
  75.     int maxD = 0;  
  76.     //遍历邻接表  
  77.     while(curPtr)  
  78.     {  
  79.         //邻居结点的id  
  80.         int toId = curPtr->toId;  
  81.         //如果当前邻居点没有处理过，那么需要借助第一遍DFS时生成的countv数组计算以当前结点id以及它的邻居结点toId组成的子树的最大深度  
  82.         if(!v[toId])  
  83.         {  
  84.             //记录  
  85.             curPtr->maxDepth = countv[toId];  
  86.             if(countv[toId] > maxD) maxD = countv[toId];  
  87.         }  
  88.         //如果当前邻居点处理过了，那需要利用当前邻居结点toId的结果来得到id的状态值  
  89.         else  
  90.         {  
  91.             //遍历toId的所有邻居toIdd。toIdd构成的子树+toId+Id作为一棵新的子树  
  92.             int maxDD = 1;  
  93.             head *tempPtr = heads[toId];  
  94.             while(tempPtr)  
  95.             {  
  96.                 int toIdd = tempPtr->toId;  
  97.                 if(toIdd != id)  
  98.                 {  
  99.                     if(tempPtr->maxDepth + 1 > maxDD)   
  100.                         maxDD = tempPtr->maxDepth + 1;  
  101.                 }  
  102.                 tempPtr = tempPtr->next;  
  103.             }  
  104.             curPtr->maxDepth = maxDD;  
  105.             if(maxDD > maxD) maxD = maxDD;  
  106.         }  
  107.         curPtr = curPtr->next;  
  108.     }  
  109.     //更新结果  
  110.     if(maxD < minDepthVal)  
  111.     {  
  112.         minDepthVal = maxD;  
  113.         num = 1;  
  114.         res[0] = id;  
  115.     }  
  116.     else if(maxD == minDepthVal)  
  117.     {  
  118.         res[num++] = id;  
  119.     }  
  120.     //DFS  
  121.     curPtr = heads[id];  
  122.     while(curPtr)  
  123.     {  
  124.         int toId = curPtr->toId;  
  125.         getAnswer(toId);  
  126.         curPtr = curPtr->next;  
  127.     }  
  128. }  
  129. int main()  
  130. {  
  131.     int i, from, to;  
  132.     int root = 1;  
  133.     while(cin>>nodeN && nodeN != NULL)  
  134.     {  
  135.         init();  
  136.         for(i = 1; i < nodeN; i++)  
  137.         {  
  138.             cin>>from>>to;  
  139.             insertEdge(from, to);  
  140.             insertEdge(to, from);  
  141.         }  
  142.         getAccount(root);  
  143.         memset(v, 0, sizeof(v));  
  144.         num = 0; minDepthVal = INT_MAX;  
  145.         getAnswer(root);  
  146.         cout<<"Answer"<<endl;  
  147.         cout<<"depth "<<minDepthVal<<endl;  
  148.         cout<<"node ";  
  149.         for(i = 0; i < num; i++)  
  150.             cout<<res[i]<<" ";  
  151.         cout<<endl;  
  152.     }  
  153.     return 0;  
  154. }  

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞