Назад

Методы программирования

Задание 6. Обходы графа

Общая информация

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

Теория

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

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

Поиском в глубину называется способ обхода вершин графа, который, начавшись от какой-либо вершины, рекурсивно применяется ко всем вершинам, в которые можно попасть из текущей. Пусть граф с N вершинами задан матрицей смежности A[N][N]. Создадим одномерный массив int visited[N] и заполним его нулями, считая, что ни одна вершина до начала выполнения алгоритма не была посещена. Функция обхода записывается следующим образом:

void go(int curr)
{
    visited[curr] = 1; /* помечаем текущую вершину как пройденную */
    for (int i = 0; i < N; i++)
        if (!visited[i] && A[curr][i])
            go(i);
}
...
/* в тексте программы */
go(start);

Распишем подробно, как будет работать алгоритм на графе, изображенном на рисунке. Пусть start = 1, т.е. начинаем с первой вершины.

Пример графа

При вызове go(1) первая вершина помечается как пройденная (visited[1] = 1), и в цикле по i перебираются все вершины, куда можно попасть из текущей (т.е. из первой). При i = 2 мы видим, что во второй вершине мы не были (visited[2] == 0) и что в графе есть ребро, соединяющее первую вершину и вторую, следовательно, рекурсивно вызываем ту же функцию go(int curr) с параметром curr, равным 2. Аналогично, go(2) вызывает go(3), а последняя вызывает go(6). Здесь мы обнаруживаем, что из шестой вершины некуда идти: и во второй, и в третьей мы уже побывали. Следовательно, go(6) дорабатывает до конца, а за ней заканчиваются go(3) и go(2). Таким образом, мы оказываемся в функции go(1) в конце цикла for при i = 2. На рисунке изображена эта ситуация, красным цветом отмечен порядок обхода вершин, жирным выделены ребра, по которым мы «ходили».

Пример графа в середине выполнения поиска в глубину

Цикл for в go(1) продолжает работу, и при i = 4 мы уходим в рекурсию go(4), и т.д. пока управление снова не вернется в go(1) (и произойдет выход из функции, т.к. больше нет непосещенных вершин, связанных ребром с первой). Окончательная картинка выглядит так:

Пример графа после выполнения поиска в глубину

В результате работы алгоритма все вершины графа оказались пройденными (при условии, что граф связный). Необходимо отметить, что ребра, по которым мы «ходили» — так называемые прямые ребра (они выделены жирным) — образуют один из возможных каркасов исходного графа.

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

При поиске в ширину вместо стека рекурсивных вызовов хранится очередь, в которую записываются вершины в порядке удаления от начальной. Опять же, введем массив int visited[N], а также создадим очередь для хранения вершин (реализуем ее в виде простого массива; естественно, возможны другие варианты). В начало очереди запишем начальную вершину:

int queue[N];
queue[0] = start;
visited[start] = 1;
int r = 0, w = 1;

Переменная r будет указывать позицию очереди, из которой мы читаем данные, переменная w — позицию, куда данные будем писать. Тогда обход может быть написан следующим образом:

while (r < w) {
    int curr = queue[r++];
    for (int i = 0; i < N; i++) {
        if (!visited[i] && A[curr][i]) {
            visited[i] = 1;
            queue[w++] = i;
        }
    }
}
Пример графа

Находясь в первой вершине, в очередь добавляются вторая и четвертая (они удалены от первой на расстояние d = 1). Затем из очереди читается очередной элемент (только что добавленная вторая вершина) и добавляются вершины, в которые можно попасть из второй: третья и шестая. То же самое делается для следующей в очереди вершины (четвертой): в очередь добавляются вершины 5, 7 и 8. Так как все вершины графа уже оказались пройденными, больше в очередь ничего добавлено не будет, и алгоритм завершится после чтения из очереди последней вершины (8).

Красным цветом на рисунке помечен порядок обхода вершин при поиске в ширину. Так как вершины перебираются в порядке удаления от начальной, работу алгоритма можно представить в виде набегающей волны, что и дает ему второе название: «метод волны». Ясно, что таким образом можно искать кратчайшие пути от одной вершины до всех остальных в невзвешенном графе (сравните с алгоритмом Дейкстры для взвешенных графов).

Лабиринты

Задачу поиска выхода из лабиринта, представленного схемой, удобно решать при помощи метода поиска в ширину. Пусть прямоугольный лабиринт представляется двумерным массивом int L[m][n], где значения L[i][j] кодируют тип клетки (i, j): свободное пространство (0), стена (1), вход (2) или выход (3). Разумеется, приведенные константы являются лишь примером одной из возможных реализаций.

Построив граф из m*n вершин (каждая вершина соответсвует одной клетке лабиринта), можно поиском в ширину найти кратчайший путь от входа к выходу. На самом деле, граф и очередь в данном случае можно даже не создавать, храня все необходимые данные в матрице L. Детали реализации задачи оставляем на усмотрение студентов.

Формулировка задания

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

Во входном файле input.txt задан связный граф (представлен любым способом). Обойти все его вершины методом поиска в глубину, вывести в файл output.txt построенный каркас графа.

b. Поиск в ширину (лабиринт)

Во входном файле input.txt задан лабиринт: размеры и схема. Найти и выдать в произвольном (но читаемом) формате в файл output.txt кратчайший путь от входа к выходу.

Пример входного и выходного файлов для задания b

Ввод: input.txt
4 5
2 1 0 0 0
0 1 0 1 0
0 1 0 1 0
0 0 0 1 3
Вывод: output.txt
x 1 x x x
x 1 x 1 x
x 1 x 1 x
x x x 1 x