Изменения
Новая страница: «==Постановка задачи== Дан ориентированный граф '''''G'''''. Требуется найти в этом графе компо…»
==Постановка задачи==
Дан [[ориентированный граф]] '''''G'''''. Требуется найти в этом графе компоненты сильной связанности.
==Алгоритм==
Данная задачи решается с помощью поиска в глубину в 3 этапа:
#Построить транспонированный граф
#Выполнить в транспонированном графе поиск в глубину и найти f[u] - время окончания обработки вершины ''u''
#Выполнить поиск глубину в '''''G''''', перебирая вершины во внешнем цикле в порядке убывания f[u]
Полученные на 3-ем этапе деревья поиска в глубину будут являться компонентами сильной связности графа '''''G'''''
Так как компоненты сильной связности исходного и транспонированного графа совпадают, то первый поиск в глубину для нахождения f[u] можно выполнить на графе '''''G''''', а второй - на транспонированном
===Доказательство===
Рассмотрим пару вершин ''s'' и ''t''.
Если вершины ''s'' и ''t'' взаимно достижимы, то они обязательно будут находиться в одном дереве поиска в глубину, поскольку, когда просматривается первая из них, вторая остаётся непосещённой и достижимой из первой и будет просмотрена, прежде чем завершится рекурсивный вызов из корня.
Теперь докажем, что если ''s'' и ''t'' находятся в одном дереве поиска, то они являются сильно связанными. Пусть ''r'' - корень этого дерева. Тогда ''s'' достижима из ''r'', из чего следует, что в обратном графе ''r'' достижима из ''s''. Но ''r'' имеет большее время окончания обработки f[r] > f[s], из чего следует что в обратном графе существует путь из ''r'' в ''s''. Тогда в исходном графе существуют пути как из ''s'' в ''r'', так и из ''r'' в ''s'', т.е. ''r'' и ''s'' сильно связаны. Те же рассуждения доказывают, что ''t'' и ''r'' сильно связаны, из чего следует что ''t'' и ''s'' также сильно связаны.
==Пример реализации==
vector<vector<int>> g, g1;
vector<int> color, ord, component;
int col;
void dfs(int & v)
{
color[v] = 1;
for (unsigned i = 0; i < g[v].size(); ++i)
{
if (color[g[v][i]] == 0)
dfs(g[v][i]);
}
ord.push_back(v);
}
void dfs2(int & v)
{
color[v] = col;
for (unsigned i = 0; i < g1[v].size(); i ++ )
{
if (color[g1[v][i]] == 0)
dfs2(g1[v][i]);
}
}
int main()
{
...
for (int i = 1; i <= n; ++i)
{
if (color[i] == 0)
dfs(i);
}
col = 1;
for (int i = ord.size(); i > 0; --i)
{
if (color[ord[i - 1]] == 0)
dfs2(ord[i - 1]), col++;
}
}
Дан [[ориентированный граф]] '''''G'''''. Требуется найти в этом графе компоненты сильной связанности.
==Алгоритм==
Данная задачи решается с помощью поиска в глубину в 3 этапа:
#Построить транспонированный граф
#Выполнить в транспонированном графе поиск в глубину и найти f[u] - время окончания обработки вершины ''u''
#Выполнить поиск глубину в '''''G''''', перебирая вершины во внешнем цикле в порядке убывания f[u]
Полученные на 3-ем этапе деревья поиска в глубину будут являться компонентами сильной связности графа '''''G'''''
Так как компоненты сильной связности исходного и транспонированного графа совпадают, то первый поиск в глубину для нахождения f[u] можно выполнить на графе '''''G''''', а второй - на транспонированном
===Доказательство===
Рассмотрим пару вершин ''s'' и ''t''.
Если вершины ''s'' и ''t'' взаимно достижимы, то они обязательно будут находиться в одном дереве поиска в глубину, поскольку, когда просматривается первая из них, вторая остаётся непосещённой и достижимой из первой и будет просмотрена, прежде чем завершится рекурсивный вызов из корня.
Теперь докажем, что если ''s'' и ''t'' находятся в одном дереве поиска, то они являются сильно связанными. Пусть ''r'' - корень этого дерева. Тогда ''s'' достижима из ''r'', из чего следует, что в обратном графе ''r'' достижима из ''s''. Но ''r'' имеет большее время окончания обработки f[r] > f[s], из чего следует что в обратном графе существует путь из ''r'' в ''s''. Тогда в исходном графе существуют пути как из ''s'' в ''r'', так и из ''r'' в ''s'', т.е. ''r'' и ''s'' сильно связаны. Те же рассуждения доказывают, что ''t'' и ''r'' сильно связаны, из чего следует что ''t'' и ''s'' также сильно связаны.
==Пример реализации==
vector<vector<int>> g, g1;
vector<int> color, ord, component;
int col;
void dfs(int & v)
{
color[v] = 1;
for (unsigned i = 0; i < g[v].size(); ++i)
{
if (color[g[v][i]] == 0)
dfs(g[v][i]);
}
ord.push_back(v);
}
void dfs2(int & v)
{
color[v] = col;
for (unsigned i = 0; i < g1[v].size(); i ++ )
{
if (color[g1[v][i]] == 0)
dfs2(g1[v][i]);
}
}
int main()
{
...
for (int i = 1; i <= n; ++i)
{
if (color[i] == 0)
dfs(i);
}
col = 1;
for (int i = ord.size(); i > 0; --i)
{
if (color[ord[i - 1]] == 0)
dfs2(ord[i - 1]), col++;
}
}
