Рубрики

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

Дан неориентированный граф, имеющий древовидные характеристики. В качестве корневого узла можно выбрать любой узел, задача которого — найти только те узлы, которые минимизируют высоту дерева.

Пример:
На диаграмме ниже все узлы сделаны как корни один за другим, мы можем видеть, что когда 3 и 4 являются корнями, высота дерева минимальна (2), поэтому {3, 4} является нашим ответом.

Мы можем решить эту проблему, сначала подумав об одномерном решении, то есть если дан самый длинный граф, то узел, который минимизирует высоту, будет средним узлом, если общее число узлов нечетным, или средним двумя узлами, если общее число узлов равно четный. Это решение может быть достигнуто следующим подходом: запустите два указателя с обоих концов пути и двигайтесь по одному шагу каждый раз, пока указатели не встретятся или не отойдут на один шаг, в конце указатели будут в тех узлах, которые минимизируют высоту, потому что мы имеем разделить узлы равномерно, чтобы высота была минимальной.
Тот же подход может быть применен и к общему дереву. Начинайте указатели со всех конечных узлов и перемещайте один шаг внутрь каждый раз, продолжая комбинировать указатели, которые перекрываются при движении, в конце только один указатель останется на некоторой вершине, или два указателя останутся на одном расстоянии. Эти узлы представляют корень вершины, которая минимизирует высоту дерева.
Таким образом, мы можем иметь только один корень или максимум два корня для минимальной высоты в зависимости от структуры дерева, как объяснено выше. Для реализации мы не будем использовать фактические указатели, вместо этого мы будем следовать BFS-подобному подходу. При запуске все листовые узлы помещаются в очередь, затем они удаляются из дерева, следующий новый листовой узел помещается в очередь, эта процедура продолжается до у нас есть только 1 или 2 узла в нашем дереве, которые представляют результат.
Поскольку мы обращаемся к каждому узлу один раз, общая временная сложность решения составляет O (n).

C ++

// 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)


Выход:

3 4

Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

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

0.00 (0%) 0 votes