Problem Statement
For an undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.
Sample Test Cases
Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/ \
2 3
Output: [1]
Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
Output: [3, 4]
Problem Solution
Gather all leaves in a queue first. At each iteration, destroy all leaves, destroy the edges that they form in the graph, then add their neighbors to the queue, iff the neighbor is a leaf.
- We initialize a queue of leaf nodes after creating the graph.
- How do we know which are leaf nodes? Keep track of in-degree using an array.
- Now, for the current queue of leaf nodes, we shall remove them from graph, then remove the edges they’re connected to, then update the in-degree of their neighbors.
- After updating the neighbor’s in-degree, see if we can add it into the queue of leaf nodes
- Repeat till we’ve 1 or 2 leaf nodes
Complexity Analysis
Time Complexity: O(n) Because each node will be processed exactly once. They go into the queue of leaves once, and they exit (at most) once.
Space Complexity: Graph creation takes O(E) space ie no of edges to be included.
Code Implementation
#include <bits/stdc++.h>
using namespace std;
// This class represents a undirected graph using adjacency list
class Graph
{
public:
int V; // No. of vertices
list<int> *adj;
vector<int> degree;
Graph(int V);
void addEdge(int v, int w);
// function to get roots which give minimum height
vector<int> rootForMinimumHeight();
};
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);
adj[w].push_back(v);
degree[v]++;
degree[w]++;
}
// 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 untill total vertex remains less than 2
while (V > 2)
{
for (int i = 0; i < q.size(); i++)
{
int t = q.front();
q.pop();
V--;
// for each neighbour, decrease its degree and
// if it become leaf, insert into queue
list<int>::iterator j;
for ( 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 to test above methods
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);
vector<int> res = g.rootForMinimumHeight();
for (int i = 0; i < res.size(); i++)
cout << res[i] << " ";
cout << endl;
}
