Алгоритмы: Алгоритм поиска компонент связности в графе | C++

Дан неориентированный граф 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 содержит список вершин в текущей компоненте связности.


Views: 540

Комментарии пока отсутcтвуют.