Разделим все вершины графа на три разновидности:

1. Вершины, про которые ничего не известно; Вершины, про которые известно, что они могут быть достигнуты из начальной вершины и которые не были обработаны. Вершины, про которые известно, что они могут быть достигнуты из начальной вершины и которые были обработаны.

В этом алгоритме три этапа - первоначальная разметка, распространение разметки и формирование результата.

Пометим все вершины первым маркером - нам про них ничего не известно

Выберем любую вершину (например первую (или нулевую)), пометим ее вторым маркером, ведь она может быть достигнута сама из себя.

Если нет вершин, помеченных вторым маркером - переходим к третьему этапу.

Выберем любую вершину, помеченную вторым маркером. Пометим ее третьим маркером. Все вершины, соседние с данной и помеченные первым маркером, пометим вторым маркером.

Повторим этот пункт с начала.

Если нужно получить список вершин, входящих в одну компоненту связности с заданной вершиной, то выбираем вершины, помеченные третьим маркером, в отдельный массив.

Если нужно получить список вершин, не входящих в одну компоненту связности с заданной вершиной, то выбираем вершины, помеченные первым маркером в отдельный массив и возвращаем полученный массив.

Если нужно просто проверить граф на связность, то считаем вершины, помеченные первым маркером, и сравниваем получившееся число с нулем. Если число вершин, помеченные первым маркером, равно нулю, то граф связный.