07.06.254. Применение обхода - justjune/AiSD2026 GitHub Wiki

Перед прочтением данного подраздела рекомендуется ознакомиться с предыдущим (см. 07.06.251. Обход в ширину)

Процедура обхода графа в ширину bfs (breadth-first traversal)(см. Скиена стр. 253) использует 3 необъявленные ранее функции: process_vertex_early(), process_vertex_late() и process_edge(). С их помощью можно настроить то, что будет делать процедура bfs при посещении каждого ребра и вершины (ибо без них она фактически ничего не делает).

*Описание структуры графа приведено на стр. 241 (листинг 7.1)

*Обход графа в ширину - алгоритм, определяющий кратчайший путь от одной вершины графа (корня) до всех остальных. Принимает сам граф и начальную вершину. Сам по себе ничего не возвращает.

Применение функций

Функция process_vertex_late()(англ. vertex - вершина) работает с текущей вершиной после её обработки и перед переходом к следующей. Конкретно в книге не приведено её применения, что видно в листинге 7.10:

void process_vertex_late(int v){ //функция, которая ничего не делает
    /* Nothing */
}

*Здесь и в последующих листингах подраздела целочисленные аргументы функций - это номера принимаемых вершин графа.

Функция process_vertex_early() работает с текущей вершиной сразу после перехода от предыдущей.

Функция process_edge()(англ. edge - ребро) работает тогда, когда текущая вершина связана с той, у которой посещены не все связанные рёбра, либо когда граф ориентированный. Принимает 2 параметра - номера текущей вершины и связанной с ней.

Возможное применение этих функций - вывод на экран всех вершин и ребер графа соответственно (листинг 7.11):

void process_vertex_early(int v){ //вывод вершин
    printf( "processed vertex %d\n", v );
}

process_edge(int x, int y){ //вывод пар "вершина-вершина", задающих рёбра
    printf( "processed edge (%d,%d)\n", x, y );
}

Функцию process_edge() также можно использовать для подсчета количества ребер графа (листинг 7.12):

process_edge(int x, int y){
    nedges = nedges + 1; //параметр nedges, разумеется, должен быть объявлен до первого вызова сей функции
}

Использование трёх вышеперечисленных функций предоставляет процедуре bfs гибкость в применении.