Задание состоит из двух частей, обе обязательны для выполнения. В первой части необходимо просто перебрать все вершины связного графа методом поиска в глубину от первой вершины и вывести ребра, вошедшие в получившийся каркас графа, во второй — реализовать поиск в ширину для решения задачи поиска выхода из заданного во входном файле лабиринта.
В этом задании рассматриваются два основных метода обхода всех вершин графа: поиск в глубину и поиск в ширину. Они весьма напоминают алгоритмы обхода деревьев, в связи с этим настоятельно рекомендуется ознакомиться с соответствующим разделом перед чтением приведенной здесь теории.
Поиском в глубину называется способ обхода вершин графа, который, начавшись
от какой-либо вершины, рекурсивно применяется ко всем вершинам, в которые
можно попасть из текущей. Пусть граф с 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.
Детали реализации задачи оставляем на усмотрение студентов.
Во входном файле input.txt задан связный граф (представлен любым способом). Обойти все его вершины
методом поиска в глубину, вывести в файл output.txt построенный каркас графа.
Во входном файле input.txt задан лабиринт: размеры и схема. Найти и выдать в произвольном
(но читаемом) формате в файл output.txt кратчайший путь от входа к выходу.
Ввод: input.txt
4 5
|
Вывод: output.txt
x 1 x x x
|