Мои Конспекты
Главная | Обратная связь

...

Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Поиск по графу в глубину и его применения





Помощь в ✍️ написании работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Алгоритм поиска описывается следующим образом: для каждой непройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них.

Пусть задан граф G = (V,E), где V — множество вершин графа, E — множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:

1. Из множества всех белых вершин выберем любую вершину, обозначим её v1.

2. Выполняем для неё процедуру DFS(v1).

3. Перекрашиваем её в чёрный цвет.

4. Повторяем шаги 1-3 до тех пор, пока множество белых вершин не пусто.

Процедура DFS (параметр — вершина )

1. Перекрашиваем вершину u в серый цвет.

2. Для всякой вершины w, смежной с вершиной u, выполняем следующие два шага:

1. Если вершина w окрашена в белый цвет, выполняем процедуру DFS(w).

2. Окрашиваем w в чёрный цвет.

Используется в качестве подпрограммы в топологической сортировке.

Ациклический граф. Топологическая сортировка

Ациклический граф — граф, в котором отсутствуют циклы, то есть пути, начинающиеся и кончающиеся в одной и той же вершине.

Топологическая сортировка — упорядочивание вершин графа согласно частичному порядку (указано какие элементы следуют за каким), заданному ребрами орграфа на множестве его вершин.

Доверь свою работу ✍️ кандидату наук!
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой



Поиск по сайту:







©2015-2020 mykonspekts.ru Все права принадлежат авторам размещенных материалов.