ALGORITHMS
Добавлен Msey,
опубликован
Дан неориентированный граф G с n вершинами и m рёбрами. Требуется найти в нём все компоненты связности, т.е. разбить вершины графа на несколько групп так, что внутри одной группы можно дойти от одной вершины до любой другой, а между разными группами — пути не существует.
Алгоритм решения:
Для решения можно воспользоваться как обходом_в_глубину, так и обходом_в_ширину.
Фактически, мы будем производить серию обходов: сначала запустим обход из первой вершины, и все вершины, которые он при этом обошёл — образуют первую компоненту связности. Затем найдём первую из оставшихся вершин, которые ещё не были посещены, и запустим обход из неё, найдя тем самым вторую компоненту связности. И так далее, пока все вершины не станут помеченными.
Итоговая асимптотика составит O(n + m): в самом деле, такой алгоритм не будет запускаться от одной и той же вершины дважды, а, значит, каждое ребро будет просмотрено ровно два раза (с одного конца и с другого конца).
Реализация на C++:
Для реализации чуть более удобным является обход в глубину:
int n;
vector<int> g[MAXN];
bool used[MAXN];
vector<int> comp;
void dfs (int v) {
used[v] = true;
comp.push_back (v);
for (size_t i=0; i<g[v].size(); ++i) {
int to = g[v][i];
if (! used[to])
dfs (to);
}
}
void find_comps() {
for (int i=0; i<n; ++i)
used[i] = false;
for (int i=0; i<n; ++i)
if (! used[i]) {
comp.clear();
dfs (i);
cout << "Component:";
for (size_t j=0; j<comp.size(); ++j)
cout << ' ' << comp[j];
cout << endl;
}
}Основная функция для вызова — find_comps(), она находит и выводит компоненты связности графа.
Мы считаем, что граф задан списками смежности, т.е. g[i] содержит список вершин, в которые есть рёбра из вершины i. Константе MAXN следует задать значение, равное максимально возможному количеству вершин в графе.
Вектор comp содержит список вершин в текущей компоненте связности.
`
ОЖИДАНИЕ РЕКЛАМЫ...
Комментарии пока отсутcтвуют.
Чтобы оставить комментарий, пожалуйста, войдите на сайт.