2. Задача поиска цепи на не взвешенных графах.

Дано: - не взвешенный граф

N₁ – начальная вершина цепи

N₂ – конечная вершина цепи.

Найти: цепь, соединяющую вершины N₁ и N₂.

Решение:

Существует два алгоритма решения данной задачи:

• Поиск в глубину

• Поиск в ширину

При поиске в глубину для каждой очередной рассматриваемой вершины берется одна смежная. Затем от одной из смежных берется следующая смежная. Затем от одной из смежных берется следующая смежная из еще не просмотренных и т.д. пока не будет найдена N₂ или не образуется тупик или не будут просмотрены все вершины.

При поиске в ширину от очередной просматриваемой вершины находятся все смежные с ней, затем последовательно просматриваются выбранные смежные, и для каждой из них определяются смежные из еще не просмотренных, пока не будет обнаружена N₂ или не будут просмотрены все вершины.

Оба алгоритма разделены на две части: прямой обратный ход. При прямом ходе ищется N₂ и одновременно формируется остовое дерево для исходного графа начиная от вершины N₁. Остовое дерево оформляется в виде списков смежности для вершин графа, т.е. в процессе алгоритма строится список смежности для остового дерева исходного графа. При обратном ходе выявляется цепь, по которой найдена N₂, начиная от вершины N₁.

Пусть граф задан дугами:

(5,2), (6,2), (7,2), (8,2), (8,3), (9,3), (10,3), (10,4), (11,4), (2,1), (3,1),(4,1)

N₁= 11          N₂= 9

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

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

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

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

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

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

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

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

7. Конец прямого хода.

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

Прямой ход:

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

1. Вершина N₁ заносится в ОЦ. В качестве ОП принимается первая вершина ОЦ.

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

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

4. Если среди смежных вершин нет вершины N₂, то в качестве вершины ОП берется следующая вершина из основной цепи. Переход к пункту 3. Иначе (т.е. вершина N₂ найдена среди смежных) конец прямого хода.

При обратном ходе необходимо проследить по списку смежности начиная с вершины N₂, относительно какой вершины была найдена данная вершина, и т.д. до начальной вершины.

Данные алгоритмы (поиск в глубину и ширину) можно использовать и для поиска циклов, при этом необходимо изменить алгоритмы так, чтобы на начальном шаге вершина N₁ не вычеркивалась из множества I.