Автор Ѐустем задал вопрос в разделе Другие языки и технологии
Кто-нибудь может объяснить алгоритм нахождения количества компонент связности? и получил лучший ответ
Ответ от Popov Dmitry[гуру]
Все очень просто.
Будем "красить" вершины, т. е. помечать их цифрами (номером компоненты связности) . Изначально все вершины покрашены в "нулевой" цвет
Берем "краску" № 1, берем первую вершину в графе, и метим ее "1", единицей же метим все вершины до которых сможем добраться из первой (тут на твой вкус - поиск в глубину или в ширину, волна тоже подойдет, хоть это и разновидность поиска в ширину)
Когда поиск закончился, ищем нераскрашенную вершину, "красим" ее в следующий цвет и все смежные с ней тоже в этот цвет
В итоге, когда все вершины будут раскрашен в ненулевой цвет, номер последнего цвета тебе и даст количество компонент связности.
Реализация за тобой 🙂