Алгоритм поиска компонент связности в графе

Дан неориентированный граф $G$ с $n$ вершинами и $m$ рёбрами. Требуется найти в нём все компоненты связности, т.е. разбить вершины графа на несколько групп так, что внутри одной группы можно дойти от одной вершины до любой другой, а между разными группами — пути не существует.

Алгоритм решения

Для решения можно воспользоваться как обходом в глубину, так и обходом в ширину.

Фактически, мы будем производить серию обходов: сначала запустим обход из первой вершины, и все вершины, которые он при этом обошёл — образуют первую компоненту связности. Затем найдём первую из оставшихся вершин, которые ещё не были посещены, и запустим обход из неё, найдя тем самым вторую компоненту связности. И так далее, пока все вершины не станут помеченными.

Итоговая асимптотика составит $O(n + m)$ : в самом деле, такой алгоритм не будет запускаться от одной и той же вершины дважды, а, значит, каждое ребро будет просмотрено ровно два раза (с одного конца и с другого конца).

Реализация

Для реализации чуть более удобным является обход в глубину:

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;
		}
}

Основная функция для вызова — $\rm find\_comps()$ , она находит и выводит компоненты связности графа.

Мы считаем, что граф задан списками смежности, т.е. $g[i]$ содержит список вершин, в которые есть рёбра из вершины $i$ . Константе $\rm MAXN$ следует задать значение, равное максимально возможному количеству вершин в графе.

Вектор $\rm comp$ содержит список вершин в текущей компоненте связности.