Dado un grafo no dirigido, que tiene características de árbol. Es posible elegir cualquier Node como raíz, la tarea es encontrar solo aquellos Nodes que minimicen la altura del árbol.
Ejemplo:
en el siguiente diagrama, todos los Nodes se crean como raíz uno por uno, podemos ver que cuando 3 y 4 son raíz, la altura del árbol es mínima (2), por lo que {3, 4} es nuestra respuesta.
Podemos resolver este problema pensando primero en la solución 1-D, es decir, si se proporciona el gráfico más largo, entonces el Node que minimizará la altura será el Node medio si el recuento total de Nodes es impar o dos Nodes medios si es total. el número de Nodes es par. Se puede llegar a esta solución mediante el siguiente enfoque: comience dos punteros desde ambos extremos de la ruta y muévase un paso cada vez hasta que los punteros se encuentren o se alejen un paso, en los punteros finales estarán en los Nodes que minimizarán la altura porque tenemos dividió los Nodes de manera uniforme para que la altura sea mínima.
El mismo enfoque se puede aplicar también a un árbol general. Inicie punteros desde todos los Nodes de hoja y muévase un paso hacia adentro cada vez, siga combinando punteros que se superponen mientras se mueve, al final solo un puntero permanecerá en algún vértice o dos punteros permanecerán a una distancia de distancia. Esos Nodes representan la raíz del vértice que minimizará la altura del árbol.
Entonces, podemos tener solo una raíz o, como máximo, dos raíces para una altura mínima, según la estructura del árbol, como se explicó anteriormente. Para la implementación, no usaremos punteros reales, sino que seguiremos un enfoque similar a BFS. Al comenzar, todos los Nodes de hoja se insertan en la cola, luego se eliminan del árbol, el siguiente Node de hoja nuevo se inserta en la cola, este procedimiento mantiene continuando hasta que tengamos solo 1 o 2 Nodes en nuestro árbol, que representan el resultado.
Implementación:
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;
}
Java
// Java program to find root which gives minimum height to
// tree
import java.io.*;
import java.util.*;
// This class represents a undirected graph using adjacency
// list representation
class Graph {
private int V; // No. of vertices
// Pointer to an array containing adjacency lists
private LinkedList<Integer>[] adj;
// List which stores degree of all vertices
private int[] degree;
@SuppressWarnings("unchecked")
public Graph(int v) // Constructor
{
V = v;
adj = new LinkedList[v];
degree = new int[v];
for (int i = 0; i < v; i++) {
adj[i] = new LinkedList<Integer>();
}
}
public void addEdge(int v, int w) // To add an edge
{
adj[v].add(w); // Add w to v’s list
adj[w].add(v); // Add v to w’s list
degree[v]++; // increment degree of v by 1
degree[w]++; // increment degree of w by 1
}
// function to get roots which give minimum height
public LinkedList<Integer> rootForMinimumHeight()
{
Queue<Integer> q = new LinkedList<>();
// first enqueue all leaf nodes in queue
for (int i = 0; i < V; i++) {
if (degree[i] == 1)
q.add(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.poll();
// for each neighbour, decrease its degree
// and if it become leaf, insert into queue
for (int j : adj[t]) {
degree[j]--;
if (degree[j] == 1)
q.add(j);
}
}
}
// copying the result from queue to result List
LinkedList<Integer> res = new LinkedList<Integer>();
while (!q.isEmpty()) {
res.add(q.poll());
}
return res;
}
}
public class GFG {
// Driver code
public static void main(String[] args)
{
Graph g = new Graph(6);
g.addEdge(0, 3);
g.addEdge(1, 3);
g.addEdge(2, 3);
g.addEdge(4, 3);
g.addEdge(5, 4);
// Function Call
LinkedList<Integer> res = g.rootForMinimumHeight();
for (int i : res)
System.out.print(i + " ");
System.out.println();
}
}
// This code is contributed by cavi4762.
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)
C#
// C# program to find root which gives minimum height to
// tree
using System;
using System.Collections.Generic;
// This class represents a undirected graph using adjacency
// list representation
class Graph {
private int V; // No. of vertices
// Pointer to an array containing adjacency lists
private List<int>[] adj;
// List which stores degree of all vertices
private List<int> degree;
public Graph(int v) // Constructor
{
V = v;
adj = new List<int>[ v ];
degree = new List<int>();
for (int i = 0; i < v; i++) {
adj[i] = new List<int>();
degree.Add(0);
}
}
public void AddEdge(int v, int w) // To add an edge
{
adj[v].Add(w); // Add w to v’s list
adj[w].Add(v); // Add v to w’s list
degree[v]++; // increment degree of v by 1
degree[w]++; // increment degree of w by 1
}
// function to get roots which give minimum height
public List<int> RootForMinimumHeight()
{
Queue<int> q = new Queue<int>();
// first enqueue all leaf nodes in queue
for (int i = 0; i < V; i++) {
if (degree[i] == 1)
q.Enqueue(i);
}
// loop until total vertex remains less than 2
while (V > 2) {
int popEle = q.Count;
V -= popEle; // popEle number of vertices will
// be popped
for (int i = 0; i < popEle; i++) {
int t = q.Dequeue();
// for each neighbour, decrease its degree
// and if it become leaf, insert into queue
foreach(int j in adj[t])
{
degree[j]--;
if (degree[j] == 1)
q.Enqueue(j);
}
}
}
// copying the result from queue to result List
List<int> res = new List<int>();
while (q.Count > 0) {
res.Add(q.Dequeue());
}
return res;
}
}
class GFG {
// Driver code
static void Main(string[] args)
{
Graph g = new Graph(6);
g.AddEdge(0, 3);
g.AddEdge(1, 3);
g.AddEdge(2, 3);
g.AddEdge(4, 3);
g.AddEdge(5, 4);
// Function Call
List<int> res = g.RootForMinimumHeight();
foreach(int i in res) Console.Write(i + " ");
Console.WriteLine();
}
}
// This code is contributed by cavi4762.
3 4
Como estamos accediendo a cada Node una vez, la complejidad temporal total de la solución es O(n).
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA