Привет, Вы узнаете о том , что такое алгоритм мальгранжа, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое алгоритм мальгранжа , настоятельно рекомендую прочитать все из категории Устройства приема и обработки радиосигналов, Передача, прием и обработка сигналов.

алгоритм мальгранжа — метод для разбиения графа на сильно связные подграфы.

Ориентированный граф (орграф) называется сильно связным (англ. strongly connected), если любые две его вершины s и t сильно связны, то есть если существует ориентированный путь из � в � и одновременно ориентированный путь из в .

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

Орграф, не принадлежащий к классу сильно связных графов, содержит некоторый набор сильно связных компонент, и некоторый набор ориентированных ребер, идущих от одной компоненты к другой.

Любая вершина орграфа сильно связна сама с собой.

Пример

Ориентированный граф с показанными компонентами сильной связности

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

Алгоритм

Пусть дан граф , где — множество вершин, в котором, ¯, а — множество дуг, описанных матрицей смежности, в котором . Об этом говорит сайт https://intellect.icu . Алгоритм разбиения заключается в следующем:

1. Для произвольной вершины находим прямое и обратное транзитивные замыкания.
2. Находим . Множество вершин этого пересечения составляют вершины максимального сильно связного подграфа.
3. Из исходного графа вычитаем подграф.
4. Граф принимаем за исходный граф и пока пункты 1, 2, 3 алгоритма повторяются.

Реализация алгоритма поиска компонент сильной связности с использованием алгоритма Мальгранжа на языке С++

Прямое транзитивное замыкание строится на основе функции dfs, которая в качестве параметров принимает списки смежности вершин g (конфигурация графа, не меняется в процессе выполнения функции), просматриваемую вершину v и список индикаторов просмотренных вершин used. В начале работы функции вершина v помечается просмотренной, а затем для каждой непосещенной вершины u, в которую существует дуга из v, функция dfs вызывается рекурсивно.

Обратное транзитивное замыкание строится на основе функции inverse_dfs. Она работает аналогично функции dfs, но рекурсивный вызов inverse_dfs осуществляется для каждой непосещенной вершины w, из которой существует дуга в вершину v. Чтобы определить, из каких вершин есть дуга в v, все вершины просматриваются на наличие в их списках смежности вершины v.

Собственно, сами транзитивные замыкания (прямое и обратное) строятся функциями find_direct_transitive и find_inverse_transitive, которые для выбранной вершины v вызывают соответственно описанные выше функции dfs и inverse_dfs и возвращают список посещенных вершин.

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

Наконец, процедура malgranzh_strong осуществляет полный поиск компонент в заданном графе. Просматриваются все вершины графа. В начале все вершины помечены непосещенными. Если очередная вершина не посещена, то для нее ищется прямое и обратное транзитивное замыкания с помощью функций find_direct_transitive и find_inverse_transitive, а затем вызывается функция find_components для этой вершины. Сама вершина и те вершины, которые вошли с ней в одну компоненту, помечаются использованными и в дальнейшем поиске компонент не участвуют. Найденная компонента запоминается в список компонент.

Текст программы, реализующей алгоритм Мальгранжа, представлен в приложении А.

Файл MalgranzhStrong.cpp:

#include <iostream>

#include <fstream>

#include <vector>

#include <list>

using namespace std;

void dfs_inverse(vector <list <int>> g, vector <bool> & used, int v)

{

used[v] = true;

for (int u = 0; u < g.size(); u++)

for (int w : g[u])

if (w == v && !used[u])

dfs_inverse(g, used, u);

}

void dfs(vector <list <int>> g, vector <bool> & used, int v)

{

used[v] = true;

for (int u : g[v])

if (!used[u])

dfs(g, used, u);

}

vector <bool> find_direct_transitive(vector <list <int>> g, int u)

{

vector <bool> used(g.size(), false);

dfs(g, used, u);

return used;

}

vector <bool> find_inverse_transitive(vector <list <int>> g, int u)

{

vector <bool> used(g.size(), false);

dfs_inverse(g, used, u);

return used;

}

void find_component(vector <bool> direct_transitive, vector <bool> inverse_transitive, vector <bool> & used, vector <int> & component)

{

for (int u = 0; u < used.size(); u++)

if (!used[u])

{

used[u] = direct_transitive[u] && inverse_transitive[u];

if (used[u])

component.push_back(u);

}

}

void malgranzh_strong(vector <list <int>> g, vector <vector <int>> & components)

{

vector <bool> used(g.size(), false);

for (int u = 0; u < g.size(); u++)

if (!used[u])

{

vector <int> component;

// Получение прямого транзитивного замыкания для вершины v

vector <bool> direct_transitive = find_direct_transitive(g, u);

// Получение обратного транзитивного замыкания для вершины v

vector <bool> inverse_transitive = find_inverse_transitive(g, u);

// Нахождение компоненты сильной связности

find_component(direct_transitive, inverse_transitive, used, component);

// Получение компоненты сильной связности

components.push_back(component);

}

}

int main()

{

ifstream rd("graph.txt");

int n;

rd >> n;

vector <list <int>> g(n);

while (!rd.eof())

{

int u, v;

rd >> u >> v;

g[u - 1].push_back(v - 1);

}

rd.close();

vector <vector <int>> components;

malgranzh_strong(g, components);

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

{

cout << "Component:";

for (int v : components[i])

cout << " " << v + 1;

cout << endl;

}

system("pause");

return 0;

}

Вау!! 😲 Ты еще не читал? Это зря!

• Алгоритм Мальгранжа
• Алгоритм Косарайю
• Алгоритм Тарьяна

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

Из статьи мы узнали кратко, но содержательно про алгоритм мальгранжа