Как вычисляется количество компонентов связности в графе?

Количество компонент связности в графе можно вычислить, например, с помощью обхода в глубину. ru.algorithmica.org Для этого нужно: ru.algorithmica.org

1. Запустить обход из первой вершины, и все вершины, которые он при этом обошёл, образуют первую компоненту связности. ru.algorithmica.org
2. Найти первую из оставшихся вершин, которые ещё не были посещены, и запустить обход из неё, найдя тем самым вторую компоненту связности. ru.algorithmica.org
3. И так далее, пока все вершины не станут помеченными. ru.algorithmica.org После этого переменная будет хранить число компонент связности, а массив — номер компоненты для каждой вершины. ru.algorithmica.org

Также количество компонент связности можно найти, используя систему непересекающихся множеств. site.ada.edu.az Для этого нужно: site.ada.edu.az

1. Изначально расположить каждую вершину в отдельном множестве. site.ada.edu.az Каждая вершина является представителем своего множества. site.ada.edu.az
2. Далее для каждого ребра (u, v) объединить множества, содержащие u и v. site.ada.edu.az
3. После обработки всех рёбер количество компонент связности будет равно числу множеств в системе непересекающихся множеств. site.ada.edu.az