Алгоритм КомпСвяз-Итер

Прочитать начало и конец очередного ребра. Далее возможны 4 различные ситуации:

1. Оба конца ребра еще не относятся ни к одной из ранее встретившихся компонент связности (mark[u]=0 и mark[v]=0). В этом случае количество компонент связности kol увеличивается на единицу, а новая компонента связности получает очередной номер ks+1.
2. Один конец ребра уже относится к какой-то компоненте связности, а второй - еще нет (mark[u]=0, а mark[v]<>0). В этом случае общее количество компонент связности kol остается прежним, а непомеченный конец ребра получает ту же пометку, что и второй его конец.
3. Оба конца нового ребра относятся к одной и той же компоненте связности (mark[u]= mark[v]<>0). В этом случае не нужно производить никаких действий.
4. Концы нового ребра относятся к разным компонентам связности (0mark[u]mark[v]0). В этом случае нужно объединить две ранее созданные компоненты связности в одну. Общее количество компонент связности kol уменьшается на 1, а все вершины, принадлежавшие к более новой компоненте связности (больший номер), получают новую пометку. Заметим, что переменная ks, обозначающая очередной свободный номер для следующей компоненты связности, в данном случае изменяться не должна, поскольку нет никакой гарантии, что изменен будет номер именно самой последней компоненты связности.

По окончании работы этого алгоритма в массиве mark будет записано S различных целых чисел, каждое из которых будет означать отдельную компоненту связности. Кроме того, в массиве могут остаться нулевые компоненты: каждая из них будет соответствовать изолированной вершине, которая тоже является отдельной компонентой связности. Следовательно, количество нулей должно быть прибавлено к количеству компонент, найденному в процессе работы основного алгоритма.

Дата добавления: 2014-01-03