Найти диаметр дерева алгоритм

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Индивидуальный проект по дискретной математике

alexvilno/calc_tree

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Нахождение центра, радиуса и диаметра дерева, заданного двоичным кодом

Алгоритм позволяет найти количество вершин, образующих центр, диаметр и радиус дерева, заданного двоичным кодом

Исходные данные берутся из файла input.txt. В первой строке записано одно число n — количество вершин в дереве. Во второй строке располагается двоичный код. Нужно записать три числа в файл output.txt количество вершин, образующих центр, радиус и диаметр.

Использованые структуры данных

Для реализиации списка смежности был использован std::vector

Корректным решением является:

• Создаем список смежности из двоичного кода
• Считаем диаметр
• Считаем радиус
• Находим центровые вершины

Создание списка смежности из двоичного кода

Для этого используем функцию

std::vectorint>> ReadTree(std::istream &in) < std::vectorint>> tree(1); ReadTreeRec(in, tree, 0); return std::move(tree); >

Она принимает в качестве аргумента входящий поток std::istream &in и создает список смежности на базе std::vector> первая его координата — рассматриваемая вершина, вторая &mdash вершина, которая ей смежна. Например список смежности для дерева, заданного двоичным кодом 0011 будет выглядеть так:

То есть по сути, наш список смежности выглядит так:

tree[c][0] = v — вершина c смежна вершине v

Создается он следующим образом:

Вызывается рекурсивная функция

void ReadTreeRec(std::istream &in, std::vectorint>> &tree, int v)

Кроме входящего потока, она принимает, собственно, список смежности, который требуется заполнить и параметр int v — индекс вершины

void ReadTreeRec(std::istream &in, std::vectorint>> &tree, int v) < for (char command; in >> command && command != '1';) < int u = tree.size(); tree.emplace_back(); //create in end tree[v].push_back(u); //create and push tree[u].push_back(v); ReadTreeRec(in, tree, u); > >

• Из входящего потока считывается двоичный код
• Если считываемый символ command != ‘1’ тогда
  • создается переменная u равная текущему размеру списка смежности — tree.size()
  • создается очередная вершина с индексом v
  • в список смежности tree[v].push_back(u) кладется смежная с ней u
  • для u делается то же самое: tree[u].push_back(v)
  • рекурсивно вызывается эта же функция, но уже от вершины с индексом u

  Довольно логично, что каждую инициализацию переменная u = tree.size() будет равна индексу очередной вершины в списке смежности

  Когда мы получили список смежности, возвращаем его без копирования return std::move(tree)

  Теперь когда мы имеем список смежности для дерева, мы можем посчитать диаметр дерева.

  Считать будем следующим образом:

  • найдем самое большое расстояние от корня дерева до крайней вершины
  • найдем самое большое расстояние от этой вершины до других вершин

  Функция, возвращающая диаметр дерева выглядит так:

  int CountDiameterLength(std::vectorint>> &tree) < int vertices_count = tree.size(); std::vectorint> distances(vertices_count); CountMaxDistanceRec(tree, distances, -1, 0); int new_root = FindVertexWithMaxDistance(distances); distances[new_root] = 0; CountMaxDistanceRec(tree, distances, -1, new_root); return distances[FindVertexWithMaxDistance(distances)]; >

  В качестве аргумента она принимает ссылку на список смежности, созданный ранее

  • int vertices_count = tree.size() запоминаем количество вершин и создаем массив такого размера std::vector distances(vertices_count)
  • заполним этот массив расстояниями от корня дерева с помощью функции void CountMaxDistanceRec(const std::vector &tree, std::vector &distances, int p, int v) — она будет описана ниже
  • от нового «нового корня» (т.е. от той вершины, расстояние до которой будет максимально) также запишем новые расстояния
  • вернем максимальное расстояние, находящееся в массиве расстояний по индексу, возвращаемому функцией FindVertexWithMaxDistance(distances) (реализациия её тривиальна, описываться не будет)

  Как работает void CountMaxDistanceRec(const std::vector> &tree, std::vector &distances, int p, int v) ?

  Она принимает ссылку на список смежности, ссылку на массив расстояний индекс родительского элемента (для корня это -1) и индекс элемента, от которого считаются расстояния

  • Проходимся по всем вершинам, кроме родительской
  • Считаем рекурсивно расстояния до всех других вершин

  То есть грубо говоря, мы прошлись DFS два раза

  Делаем это по формуле radius = (diameter + 1) / 2

  Считаем количество центров

  По формуле center = (diameter) % 2 + 1

  

  

  

  

  

  12 0001010110110001011011 

  

  

  

  

  

  Для тестов производительности есть функция, возвращающая случайное дерево из n вершин в виде двоичного кода

  std::string tree_generator(int v_count) < std::random_device random_device; std::mt19937 generator(random_device()); std::uniform_int_distribution<> distribution(0, 1); std::string generated = ""; int count_0 = 0; int count_1 = 0; for (int i = 0; i < v_count * 2; ++i) < int x = distribution(generator); if (count_0 >= v_count) < x = 1; generated += x + 48; continue; > if (x == 1 && count_1 < count_0) < generated += x + 48; ++count_1; > else if (x == 1 && count_1 >= count_0) < x = 0; generated += x + 48; ++count_0; > else < generated += x + 48; x == 1 ? ++count_1 : ++count_0; > > return generated; >

  Таблица зависимости количества вершин и времени обработки алгоритмом

  Количество	Время(SEC)
  1000	0.002
  10000	0.008
  25000	0.022
  100000	0.071
  500000	0.351
  1000000	0.894
  2000000	1.619
  3000000	2.580
  4000000	2.928
  5000000	3.587
  10000000	8.614
  25000000	20.40
  50000000	76.38

  About

  Индивидуальный проект по дискретной математике

  Источник

  Алгоритмы на деревьях

  Пусть дан граф [math]G = \langle V, E \rangle [/math] . Тогда диаметром [math]d[/math] называется [math]\max\limits_ dist(v, u)[/math] , где [math]dist[/math] — кратчайшее расстояние между вершинами.

  Алгоритм

  • Возьмём любую вершину [math] v \in V [/math] и найдём расстояния до всех других вершин. [math]d[i] = dist(v, i)[/math]
  • Возьмём вершину [math] u \in V [/math] такую, что [math]d[u] \geqslant d[t][/math] для любого [math]t[/math] . Снова найдём расстояние от [math]u[/math] до всех остальных вершин. Самое большое расстояние — диаметр дерева.

  Расстояние до остальных вершин будем искать алгоритмом [math]BFS[/math] .

  Реализация

  //граф g представлен списком смежности int diameterTree(list> g): v = u = w = 0 d = bfs(g, v) for i = 0, i < n, i++ if d[i] > d[u] u = i d = bfs(g, u) for i = 0, i < n, i++ if d[i] > d[w] w = i return d[w]

  Обоснование корректности

  Будем пользоваться свойством, что в любом дереве больше одного листа. Исключительный случай — дерево из одной вершины, но алгоритм сработает верно и в этом случае.

  После запуска алгоритма получим дерево [math]BFS[/math] .

  В дереве [math]BFS[/math] не существует ребер между вершинами из разных поддеревьев некоторого их общего предка.

  Предположим, существует ребро [math]u, v[/math] между соседними поддеревьями:

  Мы свели задачу к нахождению вершины [math]w[/math] , такой что сумма глубин поддеревьев максимальна.

  Докажем, что одно из искомых поддеревьев содержит самый глубокий лист. Пусть нет, тогда, взяв расстояние от [math]w[/math] до глубочайшего листа, мы можем улучшить ответ.

  Таким образом мы доказали, что нам нужно взять вершину [math]u[/math] с наибольшей глубиной после первого [math]BFS[/math] , очевидно, что ей в пару надо сопоставить вершину [math]w[/math] , такую что [math]dist(u, w)[/math] максимально. Вершину [math]w[/math] можно найти запуском [math]BFS[/math] из [math]u[/math] .

  Оценка времени работы

  Все операции кроме [math]BFS[/math] — [math]O(1)[/math] . [math]BFS[/math] работает за линейное время, запускаем мы его два раза. Получаем [math]O(|V| + |E|)[/math] .

  Центр дерева

  Определения

  Определение:

  Эксцентриситет вершины [math]e(v)[/math] (англ. eccentricity of a vertex) — [math]\max\limits_ dist(v, u)[/math] , где [math]V[/math] — множество вершин связного графа [math]G[/math] .

  Определение:

  Радиус [math]r(G)[/math] (англ. radius) — наименьший из эксцентриситетов вершин графа [math]G[/math] .

  Определение:

  Центральная вершина (англ. central vertex) — вершина графа [math]G[/math] , такая что [math]e(v) = r(G)[/math]

  Определение:

  Центр графа [math]G[/math] (англ. center of a graph) — множество всех центральных вершин графа [math]G[/math] .

  

  

  Алгоритм

  Наивный алгоритм

  Найдём центр графа исходя из его определения.

  • Построим матрицу [math]A_[/math] ( [math]n[/math] — мощность множества [math]V[/math] ), где [math]a_ = d_[/math] , то есть матрицу кратчайших путей. Для её построения можно воспользоваться алгоритмом Флойда-Уоршелла или Дейкстры.
  • Подсчитаем максимум в каждой строчке матрицы [math]A[/math] . Таким образом, получим массив длины [math]n[/math] .
  • Найдём наименьший элемент в этом массиве. Эта вершина и есть центр графа. В том случае, когда вершин несколько, все они являются центрами.

  Асимптотика зависит от используемого способа подсчета кратчайших путей. При Флойде это будет [math]O(V^3)[/math] , а при Дейкстре — максимум из асимптотики конкретной реализации Дейкстры и [math]O(V^2)[/math] , за которую мы находим максимумы в матрице.

  Алгоритм для дерева за O(n)

  Собственно, алгоритм нахождения центра описан в доказательстве теоремы.

  • Пройдёмся по дереву обходом в глубину и пометим все висячие вершины числом [math]0[/math] .
  • Обрежем помеченные вершины.
  • Образовавшиеся листья пометим числом [math]1[/math] и тоже обрежем.
  • Будем повторять, пока на текущей глубине не окажется не более двух листьев, и при этом в дереве будет тоже не более двух листьев.

  Оставшиеся листья являются центром дерева.

  Для того, чтобы алгоритм работал за [math]O(n)[/math] , нужно обрабатывать листья по одному, поддерживая в очереди два последовательных по глубине слоя.

  См. также

  Источники информации

  Источник

  Найдите диаметр бинарного дерева.

  Для заданного бинарного дерева напишите эффективный алгоритм для вычисления его диаметра. Диаметр бинарного дерева равен общему количеству узлов на самом длинном пути между любыми двумя его листьями.

  На следующем рисунке показаны два бинарных дерева с диаметрами 6 и 5 соответственно (узлы выделены синим цветом). Диаметр бинарного дерева, показанный слева, проходит через корневой узел, а диаметр бинарного дерева, показанный справа, не проходит через корневой узел.

  

  Простым решением было бы вычислить высоту левого и правого поддеревьев для каждого узла в дереве. максимальный путь к узлу который проходит через узел, будет иметь значение на единицу больше, чем сумма высоты его левого и правого поддеревьев. Наконец, диаметр максимален среди всех максимальное количество путей к узлам для каждого узла дерева. Временная сложность этого решения O(n 2 ) как есть n узлов в дереве, и для каждого узла мы вычисляем высоту его левого и правого поддерева, которое занимает O(n) время.

  Мы можем решить эту задачу за линейное время, выполнив обратный обход на дереве. Вместо того, чтобы вычислять высоту левого и правого поддеревьев для каждого узла в дереве, получите высоту за постоянное время. Идея состоит в том, чтобы начать с нижней части дерева и вернуть родительскому элементу высоту поддерева с корнем в данном узле. Высота поддерева с корнем в любом узле на единицу больше, чем максимальная высота левого или правого поддерева.

  Алгоритм может быть реализован следующим образом на C++, Java и Python. Здесь мы передаем диаметр по ссылке на функцию (вместо того, чтобы вернуть его) и обновить его значение внутри самой функции, используя высоту левого и правого поддерева.

  Источник

  Читайте также:  Цвет светлое дерево дуб