Анализ систем на основе топологического подхода. Выявление состава цепей. Алгоритм поиска в глубину. Задача поиска остового дерева. Определение остового дерева

Алгоритм поиска в глубину:

1.Все вершины графа заносятся в множество I – множество не просмотренных вершин.

2.Начальная вершина N1 заносится в матрицу – столбец «основная цепь» (ОЦ) в ее начальный элемент. ОЦ используется для выбора очередной просматриваемой вершины (ОП). Вершина ОП — это вершина для которой в данный момент ищется смежная вершина. В качестве вершины ОП принимается первая вершина из основной цепи, т.е. сначала это вершина цепи N1.

3.Вершина ОП вычеркивается из множества I.

4.Выявляется очередная вершина из множества I смежная с ОП. Найденная вершина заносится очередным элементом в список смежности для вершины ОП.

5. Если вершины смежной с ОП нет, то вершина ОП отмечается в ОЦ как неиспользуемая. В качестве вершины ОП принимается предшествующая вершина из ОЦ не отмеченная как неиспользуемая. Переход к этапу 3.

6.Если найденная вершина, смежная с ОП не является вершиной N2, то вершина смежная с ОП подставляется в ОЦ очередным элементом, иначе (т.е. найденная вершина – N2) переход к пункту 7.

7.В качестве новой ОП вершины берется следующая вершина из ОЦ. Переход к пункту 3.

Остовое дерево для некоторого графа — это частичный граф данного графа  не имеющий циклов. Задача построения остового дерева для структуры некоторой системы позволяет исключить из структуры дополнительные связи и оставить единственный вариант соединения любых двух вершин.

Остовое дерево формируется при работе алгоритмов поиска в глубину и ширину, поэтому для его построения можно использовать данные алгоритмы, но их необходимо заканчивать не когда будет найдена вершина N2, а когда будут вычеркнуты все вершины из множества I. При этом остовое дерево будет оформлено в виде списка смежности.

Ссылка на основную публикацию
Adblock detector