![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Поиск Эйлерова цикла в графе⇐ ПредыдущаяСтр 17 из 17
Будем рассматривать самый общий случай — случай ориентированного мультиграфа, возможно, с петлями. Также мы предполагаем, что эйлеров цикл в графе существует (и состоит хотя бы из одной вершины). Для поиска эйлерова цикла воспользуемся тем, что эйлеров цикл — это объединение всех простых циклов графа. Следовательно, наша задача — эффективно найти все циклы и эффективно объединить их в один. Реализовать это можно, например, так, рекурсивно: procedure find_all_cycles (v)var массив cycles1. пока есть цикл, проходящий через v, находим его добавляем все вершины найденного цикла в массив cycles (сохраняя порядок обхода) удаляем цикл из графа2. идем по элементам массива cycles каждый элемент cycles[i] добавляем к ответу из каждого элемента рекурсивно вызываем себя: find_all_cycles (cycles[i])Достаточно вызвать эту процедуру из любой неодиночной вершины графа, и она найдёт все циклы в графе, удалит их из графа и объединит их в один эйлеров цикл. Для поиска цикла на шаге 1 используем поиск в глубину. Сложность полученного алгоритма — O(M), то есть линейная относительно количества рёбер М в данном графе. Построение остовного дерева
Выделение связной компоненты графа. В этом алгоритме три этапа - первоначальная разметка, распространение разметки и формирование результата. 1. Первоначальная разметка Пометим все вершины первым маркером - нам про них ничего не известно. 2. Разметка соседних вершин Если нет вершин, помеченных вторым маркером - переходим к третьему этапу. 3. Завершение работы Если нужно получить список вершин, входящих в одну компоненту связности с заданной вершиной, то выбираем вершины, помеченные третьим маркером, в отдельный массив.
32)
|