Алгоритмы поиска

Search Algorithms

Хочу предложить простой, но достаточно общий взгляд на алгоритмы поиска в ширину BFS (Breadth-first Search), в глубину DFS (Depth-first Search) и бесконечное количество других с общей схемой. Фактически это алгоритмы обхода соседних вершин графа в которых последовательно строятся пути из некоторой исходной вершины ко всем остальным.
Сначала сформулируем общую схему алгоритмов этого типа. И без обычных для учебников избыточных сложностей в виде белых-серых-черных вершин.

Заводим PLAN поиска — контейнер данных, где будем хранить вершины в которых мы планируем побывать. Изначально он пуст.
Добавляем в PLAN поиска исходную вершину с которой нам предписано начать.
Пока PLAN не пуст и цель поиска не достигнута делаем следующее
1. GET: Извлекаем из PLAN какую-нибудь вершину v.
2. Посещаем вершину v. Если мы не просто обходим вершины, а что-то ищем, то здесь самое время обыскать вершину v на предмет достижения цели поиска.
3. Как-то отмечаем, что вершина v уже посещена.
4. PUT: Добавляем в PLAN все соседние с v вершины, которые еще не были посещены.
Выводим результат поиска.

Самым важным для реализации этой схемы является PLAN. Это контейнер данных в котором нам нужны две функции GET — чтобы что-то из контейнера достать и PUT — чтобы в контейнер что-то положить. Конечно лучше использовать уже готовые контейнеры. Выбор контейнера будет определять стратегию поиска.
DFS (Depth-first Search). Например, если в качестве контейнера выбрать СТЕК, то мы реализуем алгоритм поиска в глубину. Ведь организация доступа к элементам стека такова, что мы в первую очередь будем посещать те вершины, которые попали в план последними. Посмотрим на код решения задачи
Обход в глубину:

#include <iostream>
#include <stack>
using namespace std;
int main() {
    // чтение исходных данных
    int n, v;
    cin >> n >> v;
    int matrix[n][n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> matrix[i][j];
    stack <int> plan; // план посещения в виде стека
    plan.push(--v);   // мы нумеруем с 0, а не с 1
    matrix[v][v] = 1; // отмечаем, что эта вершина уже заносилась в план 
    int counter = 1;  // начальную уже сосчитали
    while (!plan.empty()) {
        v = plan.top(); // посещаем следующую по плану вершину 
        plan.pop();       // удаляем ее из плана посещения
        for (int u = 0; u < n; u++) { // перебираем соседние с ней
            if (matrix[v][u] and !matrix[u][u]) { // если новая, то
                plan.push(u);     // добавляем ее в план
                matrix[u][u] = 1; // отмечаем, что уже не новая
                counter++;        // считаем, сколько было вершин
            }
        }
    }
    cout << counter << endl;
}

#include <iostream>

#include <stack>

using namespace std;

int main() {

// чтение исходных данных

int n, v;

cin >> n >> v;

int matrix[n][n];

for (int i = 0; i < n; i++)

for (int j = 0; j < n; j++)

cin >> matrix[i][j];

stack <int> plan; // план посещения в виде стека

plan.push(--v); // мы нумеруем с 0, а не с 1

matrix[v][v] = 1; // отмечаем, что эта вершина уже заносилась в план

int counter = 1; // начальную уже сосчитали

while (!plan.empty()) {

v = plan.top(); // посещаем следующую по плану вершину

plan.pop(); // удаляем ее из плана посещения

for (int u = 0; u < n; u++) { // перебираем соседние с ней

if (matrix[v][u] and !matrix[u][u]) { // если новая, то

plan.push(u); // добавляем ее в план

matrix[u][u] = 1; // отмечаем, что уже не новая

counter++; // считаем, сколько было вершин

}

cout << counter << endl;

}

Единственное важное пояснение. Чтобы отметить, что вершина уже посещалась, я использую диагональ матрицы смежности графа. в условии специально подчеркнули, что там всегда нули, а значит я могу поставить matrix[v][v] = 1, чтобы обозначить вершину v как уже посещенную.

BFS (Breadth-first Search). Стоит нам немного изменить код и использовать для хранения плана ОЧЕРЕДЬ, алгоритм меняет стратегию и осуществляет поиск в ширину. Поскольку вершины будут посещаться в том порядке в котором мы их добавляли, это очень похоже на распространение волны из начальной точки. Отсюда другое название таких алгоритмов — заливки (flood) или волновые алгоритмы.

#include <iostream>
#include <queue>
using namespace std;
int main() {
    // чтение исходных данных
    int n, v;
    cin >> n >> v;
    int matrix[n][n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> matrix[i][j];
    queue <int> plan; // план посещения в виде очереди
    plan.push(--v);   // мы нумеруем с 0, а не с 1
    matrix[v][v] = 1; // отмечаем, что эта вершина уже заносилась в план 
    int counter = 1;  // начальную уже сосчитали
    while (!plan.empty()) {
        v = plan.front(); // посещаем следующую по плану вершину 
        plan.pop();       // удаляем ее из плана посещения
        for (int u = 0; u < n; u++) { // перебираем соседние с ней
            if (matrix[v][u] and !matrix[u][u]) { // если новая, то
                plan.push(u);     // добавляем ее в план
                matrix[u][u] = 1; // отмечаем, что уже не новая
                counter++;        // считаем, сколько было вершин
            }
        }
    }
    cout << counter << endl;
}

#include <iostream>

#include <queue>

using namespace std;

int main() {

// чтение исходных данных

int n, v;

cin >> n >> v;

int matrix[n][n];

for (int i = 0; i < n; i++)

for (int j = 0; j < n; j++)

cin >> matrix[i][j];

queue <int> plan; // план посещения в виде очереди

plan.push(--v); // мы нумеруем с 0, а не с 1

matrix[v][v] = 1; // отмечаем, что эта вершина уже заносилась в план

int counter = 1; // начальную уже сосчитали

while (!plan.empty()) {

v = plan.front(); // посещаем следующую по плану вершину

plan.pop(); // удаляем ее из плана посещения

for (int u = 0; u < n; u++) { // перебираем соседние с ней

if (matrix[v][u] and !matrix[u][u]) { // если новая, то

plan.push(u); // добавляем ее в план

matrix[u][u] = 1; // отмечаем, что уже не новая

counter++; // считаем, сколько было вершин

}

cout << counter << endl;

}

Если для хранения плана написать свой контейнер или хотя бы переопределить методы GET и PUT, то вы получите новый алгоритм поиска. Например, можно извлекать вершину из плана случайным образом. В этом случае мы получим один из рандомизированных алгоритмов семейства Монте-Карло.

Задание: Найдите все четыре места, где код поиска в глубину отличается от кода поиска в ширину.
Подсказка: Если не смогди найти четвертое отличие — оно в комментариях 🙂