Алгоритмы на графах

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

При решении многих задач, касающихся ориентированных графов, необходим эффективный метод систематического обхода вершин и дуг орграфов. Таким методом является метод поиск в глубину. Метод поиска в глубину является основой многих эффективных алгоритмов работы с графами. Предположим, что есть ориентированный граф $$G$$, в котором первоначально все вершины помечены меткой " $$unvisited$$ ". Поиск в глубину начинается с выбора начальной вершины $$v$$ орграфа $$G$$, для этой вершины метка " $$unvisited$$ " меняется на метку " $$visited$$ ". Затем для каждой вершины, смежной с вершиной $$v$$ и не посещаемой раньше, рекурсивно применяется поиск в глубину. Когда все вершины, которых можно достичь из вершины $$v$$, будут рассмотрены, поиск заканчивается. Если некоторые вершины остались не посещенными, то выбирается одна из них и алгоритм повторяется. Этот процесс продолжается до тех пор, пока не будут обойдены все вершины орграфа $$G$$.

Метод получил свое название - поиск в глубину, поскольку поиск не посещенных вершин идет в направлении вглубь до тех пор, пока это возможно. Например, пусть $$x$$ является последней посещенной нами вершиной. Выбираем очередную дугу $$(x,y)$$ (ребро), выходящую из вершины $$x$$. Возможна следующая альтернатива: вершина $$y$$ помечена меткой " $$unvisited$$ "; вершина $$y$$ помечена меткой " $$visited$$ ". Если вершина $$y$$ уже посещалась, то отыскивается другая вершина, смежная с вершиной $$x$$ ; иначе вершина $$y$$ метится меткой " $$visited$$ " и поиск начинается заново от вершины $$y$$. Пройдя все пути, которые начинаются в вершине $$y$$, возвращаемся в вершину $$x$$, то есть в ту вершину, из которой впервые была достигнута вершина $$y$$. Затем процесс повторяется, то есть продолжается выбор нерассмотренных дуг, исходящих из вершины $$x$$, и так до тех пор, пока не будут исчерпаны все эти дуги.

Алгоритм Дейкстры нахождения кратчайшего пути

Рассмотрим алгоритм нахождения путей в ориентированном графе. Пусть есть ориентированный граф $$G(V,E)$$, у которого все дуги имеют неотрицательные метки (веса дуг), а одна вершина определена как источник. Задача состоит в нахождении весов кратчайших путей от источника ко всем другим вершинам граф $$G(V,E)$$. Здесь длина пути определяется как сумма весов дуг, составляющих путь. Эта задача часто называется задачей нахождения кратчайшего пути с одним источником. Отметим, что мы будем говорить о длине пути даже тогда, когда она измеряется в других, не линейных, единицах измерения, например, во временных единицах или в денежном эквиваленте.

Можно представить орграф $$G(V,E)$$ в виде карты маршрутов рейсовых полетов из одного города в другой. Каждая вершина соответствует городу, а ребро (дуга) $$(v,w)$$ - рейсовому маршруту из города $$v$$ в город $$w$$. Вес дуги $$(v,w)$$ - это время полета из города $$v$$ в город $$w$$. В этом случае решение задачи нахождения кратчайшего пути с одним источником для ориентированного графа трактуется как минимальное время перелета между различными городами.

Для решения поставленной задачи будем использовать "жадный" алгоритм, который называют алгоритмом Дейкстры (Dijkstra). Алгоритм строит множество $$S$$ вершин, для которых кратчайшие пути от источника уже известны. На каждом шаге к множеству $$S$$ добавляется та из оставшихся вершин, расстояние до которой от источника меньше, чем для других оставшихся вершин. Если веса всех дуг неотрицательны, то можно быть уверенным, что кратчайший путь от источника к конкретной вершине проходит только через вершины множество $$S$$. Назовем такой путь особым. На каждом шаге алгоритма используется также массив $$M$$, в который записываются длины кратчайших особых путей для каждой вершины. Когда множество $$S$$ будет содержать все вершины орграфа, то есть для всех вершин будут найдены особые пути, тогда массив $$M$$ будет содержать длины кратчайших путей от источника к каждой вершине.

Алгоритм Флойда нахождения кратчайших путей между парами вершин

Предположим, что мы имеем помеченный орграф, который содержит время полета по маршрутам, связывающим определенные города, и~мы хотим построить таблицу, где приводилось бы минимальное время перелета из одного (произвольного) города в любой другой. В этом случае мы сталкиваемся с общей задачей нахождения кратчайших путей, то есть нахождения кратчайших путей между всеми парами вершин орграфа.

Формулировка задачи.Есть ориентированный граф $$G(V,E)$$, каждой дуге (ребру) $$(v,w)$$ этого графа сопоставлен неотрицательный вес $$C_{vw}$$. Общая задача нахождения кратчайших путей заключается в нахождении для каждой упорядоченной пары вершин $$v,w$$ любого пути от вершины $$v$$ в вершину $$w$$, длина которого минимальна среди всех возможных путей от $$v$$ к $$w$$ .

Можно решать эту задачу, последовательно применяя алгоритм Дейкстры для каждой вершины, объявляемой в качестве источника. Но мы для решения поставленной задачи воспользуемся алгоритмом, предложенным Флойдом (R.W. Floyd). Пусть все вершины орграфа последовательно пронумерованы от 1 до $$n$$. Алгоритм Флойда использует матрицу $$A(n \times n)$$, в которой находятся длины кратчайших путей:

$$A_{ij} = C_{ij}$$, если $$i \ne j$$ ;

$$A_{ij} = 0$$, если $$i = j$$ ;

$$A_{ij} = \infty$$ если отсутствует путь из вершины $$i$$ в вершину $$j$$.

Над матрицей $$A$$ выполняется $$n$$ итераций. После $$k$$ -й итерации $$A_{ij}$$ содержит значение наименьшей длины пути из вершины $$i$$ в вершину $$j$$, причем путь не проходит через вершины с номерами большими $$k$$.

Вычисление на $$k$$ -ой итерации выполняется по формуле: $$A_{ij}^k = \min (A_{ij}^{k - 1},A_{ik}^{k - 1},A_{kj}^{k - 1} )$$ Верхний индекс $$k$$ обозначает значение матрицы $$A$$ после $$k$$ -ой итерации.

Для вычисления $$A_{ij}^k$$ проводится сравнение величины $$A_{ij}^{k -1}$$ (то есть стоимость пути от вершины $$i$$ к вершине $$j$$ без участия вершины $$k$$ или другой вершины с более высоким номером) с величиной $$A_{ik}^{k - 1} + A_{kj}^{k - 1}$$ (стоимость пути от вершины $$i$$ к вершине $$k$$ плюс стоимость пути от вершины $$k$$ до вершины $$j$$ ). Если путь через вершину $$k$$ дешевле, чем $$A_{ij}^{k - 1}$$, то величина $$A_{ij}^k$$ изменяется. Рассмотрим орграф:

Матрица A(3 * 3) на нулевой итерации (k = 0)

Матрица A(3 * 3) после первой итерации (k = 1)

Матрица A(3 * 3) после второй итерации (k = 2)

Матрица A(3 * 3) после третьей итерации (k = 3)

Программы

Программа 1. Построение матрицы инциндентности.

//Построение матрицы инциндентности
//Программа реализована на языке программирования Turbo-C++

\begin{verbatim}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <iostream.h>

struct elem
{
    int num;  /* Номер вершины */
    int suns; /* Количество сыновей */
    char str[20]; /* Строка с номерами сыновей */
    elem *next; /* Указатель на следующую вершину */
} *head, *w1, *w2;

int Connected(int i, int j)
{
    int k;
    char *str1;
    w2 = head;
    if(i == j) return 0;
    for(k=1; k<i; k++)
        w2 = w2->next;
    if( strchr(w2->str, j) ) return 1;
    return 0;
}

void main()
{

int tops;
    int i,j,k,l;
    char *str1;

clrscr();
    printf("Введите количество вершин  \n");
    scanf("%d", tops);

head = (elem *)malloc(sizeof(elem));
    head->num = 1;
    head->suns = 0;
    head->str[0] = '\0';
    head->next = NULL;

w1 = head;

for(i=2;i<=tops;i++)
    {
        w2 = (elem *)malloc(sizeof(elem));
        w2->num = i;
        w2->suns = 0;
        w2->str[0] = '\0';
        w2->next = NULL;

w1->next = w2;
        w1 = w2;
    }

w1 = head;

for(i=1; i<=tops; i++)
    {
//      clrscr();
        printf("Введите количество путей из вершины  %d\n", i);
        scanf("%d", k);

for(j=1; j<=k; j++)
        {
            printf("Введите связь %d\n", j);
            scanf("%d", l);
            if((l<=0) || (l > tops))
            {
                printf("Такой вершины нет, повторите попытку\n");
                l = 0;
                j--;
                continue;
            }
            w1->str[w1->suns++] = l;
            w1->str[w1->suns] = '\0';
            if(w1->suns == 49)
            {
                printf("Слишком много связей !");
                exit(1);
            }
        }
        w1 = w1->next;
    }
    clrscr();
    printf("\n\n Матрица инциндентности :\n");
    for(i=1; i<=tops; i++)
    {
        printf("\n %d) ", i);
        for(j=1; j<=tops; j++)
        {
            printf("%d ", Connected(i, j));
        }
    }
    printf("\n\n Нажмите любую клавишу\ldots ");
    getch();
}