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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова .
Аналогично, осуществляем возврат до вершины 1. После рассмотрения
всех возможных путей через вершину 2, остаются пути, которые проходят че-
рез вершину 4. Из всех возможных путей (1->4->3->2, 1->4->3->6 и
1->4->5) искомым путем является 1->4->3->6. Таким образом, найдены
все возможные пути из вершины 1 в вершину 6.
Функция AllWays реализует рекурсивный вариант этого алгоритма. Па-
раметрами функции являются исходный граф в виде матрицы смежности g,
номера начальной вершины s и конечной вершины t, массив пометок вер-
шин графа x, номер текущей вершины в строящемся пути k и длина уже по-
строенного пути sum. Пометка в массиве x представляет собой номер верши-
ны в построенном пути, например, x[3]=2 означает, что вершина 3 в по-
строенном пути является второй.
// определение рекурсивной функции поиска всех путей
// в графе, соединяющих две заданные вершины
void AllWays(Graph2 g,int s, int t, int* x, int k, int sum)
{
int i,j,nom;
s--; t--;
// указываем, что порядковый номер s-ой вершины графа
// в строящемся пути равен k
x[s]=k;
// условие выхода из рекурсии –
// проверка достижения конечной вершины пути
if(s==t)
{
// цикл распечатки найденного пути
nom=1;
while(true)
{
for(i=0;i<g.n;i++)
if(x[i]==nom)
{
printf("%d",i+1);
break;
}
if(i==b) break;
printf("->");
nom++;
}
printf(" sum=%d\n",sum);
x[s]=0;
114
А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова                   .
    Аналогично, осуществляем возврат до вершины 1. После рассмотрения
всех возможных путей через вершину 2, остаются пути, которые проходят че-
рез вершину 4. Из всех возможных путей (1->4->3->2, 1->4->3->6 и
    1->4->5) искомым путем является 1->4->3->6. Таким образом, найдены
все возможные пути из вершины 1 в вершину 6.
    Функция AllWays реализует рекурсивный вариант этого алгоритма. Па-
раметрами функции являются исходный граф в виде матрицы смежности g,
номера начальной вершины s и конечной вершины t, массив пометок вер-
шин графа x, номер текущей вершины в строящемся пути k и длина уже по-
строенного пути sum. Пометка в массиве x представляет собой номер верши-
ны в построенном пути, например, x[3]=2 означает, что вершина 3 в по-
строенном пути является второй.
    // определение рекурсивной функции поиска всех путей
    // в графе, соединяющих две заданные вершины
    void AllWays(Graph2 g,int s, int t, int* x, int k, int sum)
    {
        int i,j,nom;
        s--; t--;
        // указываем, что порядковый номер s-ой вершины графа
        // в строящемся пути равен k
        x[s]=k;

           // условие выхода из рекурсии –
           // проверка достижения конечной вершины пути
           if(s==t)
           {
                 // цикл распечатки найденного пути
                 nom=1;
                 while(true)
                 {
                      for(i=0;i");
                      nom++;
                 }
                 printf(" sum=%d\n",sum);
                 x[s]=0;

                                           114

Страницы