| Проверка связности графа с ненаправленными ребрами. Выделение связной компоненты графа |
|
|
Разделим все вершины графа на три разновидности:
- Вершины, про которые ничего не известно;
Вершины, про которые известно, что они могут быть достигнуты из начальной
вершины и которые не были обработаны.
Вершины, про которые известно, что они могут быть достигнуты из начальной
вершины и которые были обработаны.
|
Выделение связной компоненты графа. |
|
|
В этом алгоритме три этапа - первоначальная разметка, распространение
разметки и формирование результата.
|
1. Первоначальная разметка |
|
|
Пометим все вершины первым маркером - нам про них ничего не известно
Выберем любую вершину (например первую (или нулевую)),
пометим ее вторым маркером, ведь она может быть достигнута сама из себя.
|
2. Разметка соседних вершин |
|
|
Если нет вершин, помеченных вторым маркером - переходим к третьему этапу.
Выберем любую вершину, помеченную вторым маркером.
Пометим ее третьим маркером. Все вершины,
соседние с данной и помеченные первым маркером, пометим вторым маркером.
Повторим этот пункт с начала.
|
3. Завершение работы |
|
|
Если нужно получить список вершин, входящих в одну компоненту связности с
заданной вершиной, то выбираем вершины,
помеченные третьим маркером, в отдельный массив.
Если нужно получить список вершин, не входящих в одну компоненту
связности с заданной вершиной, то выбираем вершины,
помеченные первым маркером в отдельный массив и возвращаем полученный
массив.
Если нужно просто проверить граф на связность, то считаем вершины,
помеченные первым маркером, и сравниваем получившееся число с нулем.
Если число вершин, помеченные первым маркером, равно нулю, то граф связный.Обсудить на форуме »
|
Комментарии для веб-мастера |
|
|
|
Copyright 2000-2002 © Ilia Kantor, при поддержке проекта MANUAL.RU
|
