最近看到一道谷歌笔试题,“已知一颗无向无环连通图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)
*/
- #include <iostream>
- #define MAX_N 100
- using namespace std;
- struct head //邻接表
- {
- int toId; //边的to结点的id
- int maxDepth; //表示以i为树根,连通j所带子树的最大深度
- head *next;
- head()
- {
- toId = maxDepth = 0;
- next = NULL;
- }
- }*heads[MAX_N];
- int countv[MAX_N]; //第一遍DFS时记录以当前节点作为子树的最大深度+1
- int res[MAX_N], num, minDepthVal; //记录最终结果,具有最小最大度数minDepthVal的结点个数num以及分别是哪些结点
- bool v[MAX_N]; //标记结点是否被访问了
- int nodeN; //结点个数
- //初始化
- void init()
- {
- for(int i = 0; i < MAX_N; i++)
- {
- countv[i] = res[i] = 0;
- v[i] = false;
- head *curPtr = heads[i];
- while(curPtr != NULL)
- {
- head *tempPtr = curPtr->next;
- delete curPtr;
- curPtr = tempPtr;
- }
- heads[i] = NULL;
- }
- }
- //向临街表中插入一条边
- void insertEdge(int from, int to)
- {
- head *newHead = new head();
- newHead->toId = to;
- newHead->next = heads[from];
- heads[from] = newHead;
- }
- //第一遍DFS计算Account
- int getAccount(int id)
- {
- //标记访问
- v[id] = true;
- //最大深度+1的初始值为1
- int maxD = 1;
- //遍历当前结点的临街表
- head *curPtr = heads[id];
- while(curPtr)
- {
- //邻接点id
- int toId = curPtr->toId;
- curPtr = curPtr->next;
- if(v[toId]) continue;
- int tempD = getAccount(toId);
- //更新最大深度+1的值
- if(tempD + 1 > maxD) maxD = tempD + 1;
- }
- //记录结果
- return countv[id] = maxD;
- }
- //第二遍DPF计算以每个结点为根得到的树的最大深度
- void getAnswer(int id)
- {
- //如果访问过就不再访问
- if(v[id]) return;
- //标记未访问结点为访问状态
- v[id] = true;
- head *curPtr = heads[id];
- //孤立点的最大深度是0,所以maxD的初始值为0
- int maxD = 0;
- //遍历邻接表
- while(curPtr)
- {
- //邻居结点的id
- int toId = curPtr->toId;
- //如果当前邻居点没有处理过,那么需要借助第一遍DFS时生成的countv数组计算以当前结点id以及它的邻居结点toId组成的子树的最大深度
- if(!v[toId])
- {
- //记录
- curPtr->maxDepth = countv[toId];
- if(countv[toId] > maxD) maxD = countv[toId];
- }
- //如果当前邻居点处理过了,那需要利用当前邻居结点toId的结果来得到id的状态值
- else
- {
- //遍历toId的所有邻居toIdd。toIdd构成的子树+toId+Id作为一棵新的子树
- int maxDD = 1;
- head *tempPtr = heads[toId];
- while(tempPtr)
- {
- int toIdd = tempPtr->toId;
- if(toIdd != id)
- {
- if(tempPtr->maxDepth + 1 > maxDD)
- maxDD = tempPtr->maxDepth + 1;
- }
- tempPtr = tempPtr->next;
- }
- curPtr->maxDepth = maxDD;
- if(maxDD > maxD) maxD = maxDD;
- }
- curPtr = curPtr->next;
- }
- //更新结果
- if(maxD < minDepthVal)
- {
- minDepthVal = maxD;
- num = 1;
- res[0] = id;
- }
- else if(maxD == minDepthVal)
- {
- res[num++] = id;
- }
- //DFS
- curPtr = heads[id];
- while(curPtr)
- {
- int toId = curPtr->toId;
- getAnswer(toId);
- curPtr = curPtr->next;
- }
- }
- int main()
- {
- int i, from, to;
- int root = 1;
- while(cin>>nodeN && nodeN != NULL)
- {
- init();
- for(i = 1; i < nodeN; i++)
- {
- cin>>from>>to;
- insertEdge(from, to);
- insertEdge(to, from);
- }
- getAccount(root);
- memset(v, 0, sizeof(v));
- num = 0; minDepthVal = INT_MAX;
- getAnswer(root);
- cout<<"Answer"<<endl;
- cout<<"depth "<<minDepthVal<<endl;
- cout<<"node ";
- for(i = 0; i < num; i++)
- cout<<res[i]<<" ";
- cout<<endl;
- }
- return 0;
- }