Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 113 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

. Практикум по курсу «Алгоритмизация и программирование». Часть 2
Задача 3. Дан граф в виде матрицы смежности. Определить длины всех
путей из узла А в узел В.
Разберем два варианта решения этой задачи – рекурсивный и нерекурсив-
ный.
Идея алгоритма в обоих случаях заключается в следующем. Находясь в
некоторой текущей вершине A, последовательно переходим в каждую из
смежных с ней вершин. Каждую пройденную вершину помечаем как верши-
ну, включенную в путь, и одновременно добавляем длину соответствующего
ребра к длине строящегося пути. Таким образом, все вершины фактически
разделены на две группы: уже включенные в путь и оставшиеся. Теперь зада-
ча сводится к нахождению всех путей из последней помеченной вершины в
конечную, при этом рассматриваются только те смежные с ней вершины, ко-
торые еще не включены в путь. Если на каком-то этапе достигается конечная
вершина, печатаем путь.
Если для некоторой вершины все пути рассмотрены, снимаем с нее по-
метку и возвращаемся в предыдущую вершину, продолжая поиск оставшихся
путей из нее.
Например, пусть дан граф, изображенный на рис. 7.5.
Рис. 7.5. Пример графа.
Требуется найти все пути из вершины 1 в вершину 6. Помечаем вершину
1 как включенную в путь. Для нее существуют две смежные вершины – 2 и 4.
Сначала переходим в вершину 2 и помечаем ее. Теперь задача свелась к поис-
ку всех путей из вершины 2 в вершину 6. Для текущей вершины 2 смежными
являются две – 1 и 3. Однако вершина 1 уже включена в путь, поэтому ее не
рассматриваем и переходим в вершину 3. Из нее сначала находится путь 3->4-
>5. Вершина 5 не имеет непомеченных смежных вершин, поэтому возвраща-
емся в вершину 4. Для нее нерассмотренных возможных путей больше нет.
Поэтому возвращаемся в вершину 3, для которой существует еще одна не-
рассмотренная и непомеченная смежная вершина 6. Таким образом, найден
путь из начальной вершины в конечную (1->2->3->6).
113
            .       Практикум по курсу «Алгоритмизация и программирование». Часть 2
    Задача 3. Дан граф в виде матрицы смежности. Определить длины всех
путей из узла А в узел В.
    Разберем два варианта решения этой задачи – рекурсивный и нерекурсив-
ный.
    Идея алгоритма в обоих случаях заключается в следующем. Находясь в
некоторой текущей вершине A, последовательно переходим в каждую из
смежных с ней вершин. Каждую пройденную вершину помечаем как верши-
ну, включенную в путь, и одновременно добавляем длину соответствующего
ребра к длине строящегося пути. Таким образом, все вершины фактически
разделены на две группы: уже включенные в путь и оставшиеся. Теперь зада-
ча сводится к нахождению всех путей из последней помеченной вершины в
конечную, при этом рассматриваются только те смежные с ней вершины, ко-
торые еще не включены в путь. Если на каком-то этапе достигается конечная
вершина, печатаем путь.
    Если для некоторой вершины все пути рассмотрены, снимаем с нее по-
метку и возвращаемся в предыдущую вершину, продолжая поиск оставшихся
путей из нее.
    Например, пусть дан граф, изображенный на рис. 7.5.




                             Рис. 7.5. Пример графа.
    Требуется найти все пути из вершины 1 в вершину 6. Помечаем вершину
1 как включенную в путь. Для нее существуют две смежные вершины – 2 и 4.
Сначала переходим в вершину 2 и помечаем ее. Теперь задача свелась к поис-
ку всех путей из вершины 2 в вершину 6. Для текущей вершины 2 смежными
являются две – 1 и 3. Однако вершина 1 уже включена в путь, поэтому ее не
рассматриваем и переходим в вершину 3. Из нее сначала находится путь 3->4-
>5. Вершина 5 не имеет непомеченных смежных вершин, поэтому возвраща-
емся в вершину 4. Для нее нерассмотренных возможных путей больше нет.
Поэтому возвращаемся в вершину 3, для которой существует еще одна не-
рассмотренная и непомеченная смежная вершина 6. Таким образом, найден
путь из начальной вершины в конечную (1->2->3->6).

                                     113

Страницы