Monthly Archives: Март 2015

1999

Цитата из Википедии: 28 марта 1999 «во время митинга против бомбежек Сербии авиацией НАТО в Москве здание посольства США попытались обстрелять из гранатомета. После проведения митинга зданию потребовался серьезный косметический ремонт в связи с тем, что были выбиты стекла и забрызган разноцветной краской почти весь фасад».

Операция НАТО против Сербии началась 24 марта. Летевший в тот день в США Примаков, узнав о начале операции, развернул самолёт и вернулся в Россию. Мне кажется, что этот разворот в полёте символизирует дальнейший разворот курса страны в целом, начавшийся с операции «преемник», и изменения образа мыслей многих в России (в частности, моего — именно с той весны). Ореол американцев-«друзей» развеялся. Вера в декларируемое на Западе верховенство закона и «международное право» была поколеблена. Мы смогли осознать свою былую наивность. Возможно, нам повезло, что в своей жадности «мировой гегемон» поспешил начать самоутверждаться, не дождавшись доведения РФ до «кондиции».

Напоследок карта (взята с Википедии) мест использования боеприпасов на основе обеднённого урана в Косово. Такие вот «спасители угнетённого народа».

Косово, обеднённый уран

О реализации одного алгоритма топологической сортировки

Как-то так получилось, что именно записи на в общем-то побочную для меня тему алгоритмов на графах привлекают основной объём посещений блога «со стороны». Отчасти поэтому, а также потому, что на лекции я предложил было не слишком разумный вариант реализации одного из алгоритмов топологической сортировки вершин ориентированного ациклического графа (DAG — «directed acyclic graph»), я решил написать данный текст и соответствующий код.

На изображении ниже представлен DAG, использованный для проверки реализованной программы.

Пример DAG

Пример DAG

Рассматриваемый алгоритм весьма прост. Его можно описать следующим образом.

Вход: граф G = (V, E).
Выход: последовательность R.
Пусть R = ∅.
Пока |R| < |V|:
    пусть v ∈ V \ R такая что indeg(v) = 0;
    дописать v к R;
    удалить v из G.

Хотя этот алгоритм описан как «деструктивный» по отношению к графу G, на практике совсем не обязательно «разрушать» пусть даже копию некоторого представления G. Его можно переформулировать следующим образом (предполагая представление графа в виде списков соседей).

Создать A = [ indeg(v) | v ∈ V ] — массив степений захода вершин.
Завести очередь Q и поместить туда все v ∈ V: A[v] = 0;
Пока Q ≠ ∅:
    извлечь очередную v из Q;
    поместить v в R;
    для всех w ∈ out(v):
        если A[w] = 1: поместить w в Q;
        если A[w] > 0: A[w] := A[w] – 1.

Как нетрудно видеть, данный алгоритм имеет сложность O(|V| + |E|), при предположении, что затраты на перечисление соседей вершины пропорциональны их количеству. Никакие «сложные» структуры данных не используются.

Ссылка на реализацию на C++.