Задание состоит из двух частей, обе обязательны для выполнения. В первой части необходимо просто перебрать все вершины связного графа методом поиска в глубину от первой вершины и вывести ребра, вошедшие в получившийся каркас графа, во второй — реализовать поиск в ширину для решения задачи поиска выхода из заданного во входном файле лабиринта.
В этом задании рассматриваются два основных метода обхода всех вершин графа: поиск в глубину и поиск в ширину. Они весьма напоминают алгоритмы обхода деревьев, в связи с этим настоятельно рекомендуется ознакомиться с соответствующим разделом перед чтением приведенной здесь теории.
Поиском в глубину называется способ обхода вершин графа, который, начавшись
от какой-либо вершины, рекурсивно применяется ко всем вершинам, в которые
можно попасть из текущей. Пусть граф с 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
|