Корни дерева, которые дают минимальную высоту

// C ++ программа для поиска корня, который дает минимальную высоту дерева
#include <bits/stdc++.h>

using namespace std;

  
// Этот класс представляет неориентированный граф, используя список смежности
// представление

class Graph

{

public:

    int V; // Количество вершин

    // Указатель на массив, содержащий списки смежности

    list<int> *adj;

    // Вектор, который хранит степень всех вершин

    vector<int> degree;

    Graph(int V);            // Конструктор

    void addEdge(int v, int w);   // Добавить ребро

    // функция для получения корней, которые дают минимальную высоту

    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 добавляет вершину в список смежности и увеличивает
// степень на 1

void Graph::addEdge(int v, int w)

{

    adj[v].push_back(w);    // Добавить w в список v

    adj[w].push_back(v);    // Добавить v в список w

    degree[v]++;            // увеличиваем степень v на 1

    degree[w]++;            // увеличиваем степень w на 1

}

  
// Метод возврата корней, который дает минимальную высоту дерева

vector<int> Graph::rootForMinimumHeight()

{

    queue<int> q;

    // сначала ставим все конечные узлы в очередь

    for (int i = 0; i < V; i++)

        if (degree[i] == 1)

            q.push(i);

    // цикл до полной вершины остается меньше 2

    while (V > 2)

    {

        for (int i = 0; i < q.size(); i++)

        {

            int t = q.front();

            q.pop();

            V--;

            // для каждого соседа уменьшить его степень и

            // если он стал листом, вставляем в очередь

            for (auto j = adj[t].begin(); j != adj[t].end(); j++)

            {

                degree[*j]--;

                if (degree[*j] == 1)

                    q.push(*j);

            }

        }

    }

    // копируем результат из очереди в вектор результатов

    vector<int> res;

    while (!q.empty())

    {

        res.push_back(q.front());

        q.pop();

    }

    return res;

}

  
// Код драйвера для тестирования вышеуказанных методов

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;

}

# Python программа для поиска root, которая дает минимум
# высота до дерева

  
# Этот класс представляет неориентированный граф, используя
# представление списка смежности

class Graph:

    # Конструктор графа, инициализировать список смежности

    # и вектор степени

    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)

        # Строки ниже позволяют нам определять методы снаружи

        # определения класса

        # Проверьте http://bit.ly/2e5HfrW для лучшего объяснения

        Graph.addEdge = addEdge

        Graph.rootForMinimumHeight = rootForMinimumHeight

  
# addEdge метод добавляет вершину в список смежности и
# увеличивает степень на 1

def addEdge(self, v, w):

    self.adj[v].append(w) # Добавляет w в список v

    self.adj[w].append(v) # Добавляет v в список w

    self.degree[v] += 1      # степень приращения v на 1

    self.degree[w] += 1      # степень приращения w на 1

  
# Метод возврата корней, который дает минимальную высоту дерева

def rootForMinimumHeight(self):

    from Queue import Queue

    q = Queue()

    # Сначала поставьте в очередь все конечные узлы в очереди

    for i in range(self.V):

        if self.degree[i] == 1:

            q.put(i)

    # цикл до тех пор, пока общая вершина не станет меньше 2

    while(self.V > 2):

        for i in range(q.qsize()):

            t = q.get()

            self.V -=1 

            # для каждого соседа, уменьшите его степень и

            # если это станет листом, вставьте в очередь

            for j in self.adj[t]:

                self.degree[j] -= 1 

                if self.degree[j] == 1:

                    q.put(j)

    # Копирование результата из очереди в вектор результатов

    res = list()

    while(q.qsize() >  0):

        res.append(q.get())

    return res

  
# Код драйвера для тестирования вышеуказанных методов

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)

res = g.rootForMinimumHeight()

for i in res:

    print i,

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)