Топологическая сортировка

 

Под топологической сортировкой понимается сортировка элементов, для которых определен частичный порядок, т.е. упорядочивание задано не для всех, а только для некоторых пар элементов.
Задача топологической сортировки графа состоит в следующем: указать такой линейный порядок на его вершинах, чтобы любое ребро вело от вершины с меньшим номером к вершине с большим номером. Очевидно, что если в графе есть циклы, то такого порядка не существует.

*-Нравится статья? Кликни по рекламе! :)

Бинарные деревья

Бинарное дерево представляет собой структуру, в которой каждый узел (или вершина) имеет не более двух узлов-потомков и в точности одного родителя. Самый верхний узел дерева является единственным узлом без родителей; он называется корневым узлом. Бинарное дерево
с N узлами имеет не меньше [log₂N + 1] уровней (при максимально плотной упаковке узлов).
Если уровни дерева занумеровать, считая что корень лежит на уровне 1, то на уровне с номером К лежит 2^К-1 узел. У полного бинарного дерева с j уровнями (занумерованными от 1 до j) все листья лежат на уровне с номером j, и у каждого узла на уровнях с первого по j — 1
в точности два непосредственных потомка. В полном бинарном дереве с j уровнями 2^j — 1 узел.
*-Нравится статья? Кликни по рекламе! :)

Алгоритм Прима

Предлагаю чуточку отвлечься от Sython'a (я так называю реализацию SICP на Python))))
Итак рассмотрим один из простых но очень классических алгоритмов - алгоритм Прима поиска минимальных остовного дерева.
Советую так же ознакомиться со статьей Теория графов и деревьев для Python

Описание

Дан взвешенный неориентированный граф с вершинами и рёбрами. Требуется найти такое поддерево этого графа, которое бы соединяло все его вершины, и при этом обладало наименьшим возможным весом (т.е. суммой весов рёбер). Поддерево — это набор рёбер, соединяющих все вершины, причём из любой вершины можно добраться до любой другой ровно одним простым путём.
*-Нравится статья? Кликни по рекламе! :)

Теория графов и деревьев для Python

 Многие задачи, например, задача обхода точек по кратчайшему маршруту, могут быть решены с помощью одного из мощнейших инструментов — с помощью графов. Часто, если вы можете определить, что решаете задачу на графы, вы по-крайней мере на полпути к решению. А если ваши данные можно каким-либо образом представить как деревья, у вас есть все шансы построить действительно эффективное решение.
Графами можно представить любую структуру или систему, от транспортной сети до сети передачи данных и от взаимодействия белков в ядре клетки до связей между людьми в Интернете.
*-Нравится статья? Кликни по рекламе! :)

Деревья кодирования по Хаффману

Эта статья дает возможность попрактиковаться в использовании списковых структур и абстракции данных для работы с множествами и деревьями.
Советую ознакомиться с предыдущей записью: Представление множеств и КодХаффмана
Они применяются к методам представления данных как последовательностей из единиц и нулей (битов). Например, стандартный код ASCII, который используется для представления текста в компьютерах, кодирует каждый символ как последовательность из семи бит. Семь бит позволяют нам обозначить 2⁷, то есть 128 различных символов. В общем случае, если нам требуется различать n символов, нам потребуется log₂N бит для каждого символа.
*-Нравится статья? Кликни по рекламе! :)