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

#Пред-обработка вершины (process_vertex_early)

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

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

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

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

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

process_vertex_early(v) вызывается, когда вершина v взята из очереди, но её рёбра ещё не просмотрены. То есть это обработка вершины "на входе".

process_edge(x, y) вызывается для ребра между текущей вершиной x и её соседом y. Ребро обрабатывается, если вершина y ещё не обработана, либо если граф ориентированный. Из-за этого в неориентированном графе каждое ребро обрабатывается один раз.

process_vertex_late(v) вызывается, когда все рёбра вершины v уже просмотрены. В книге она ничего не делает (листинг 7.10), потому что вся обработка вершин пока происходит на входе, в process_vertex_early():

void process_vertex_late(int v) {
    /* Нет действий */
}

Вывод вершин и рёбер

Следующие функции выводят на экран каждую вершину и каждое ребро по одному разу (листинг 7.11):

void process_vertex_early(int v) {
    printf("processed vertex %d\n", v);
}

void process_edge(int x, int y) {
    printf("processed edge (%d,%d)\n", x, y);
}

Подсчёт рёбер

Через process_edge() можно ещё посчитать количество рёбер графа (листинг 7.12):

void process_edge(int x, int y) {
    nedges = nedges + 1;
}

Переменная nedges, конечно, должна быть объявлена и обнулена до запуска bfs.

Пример

Возьмём неориентированный граф из 4 вершин с рёбрами 1-2, 1-3, 2-4, 3-4 и запустим bfs из вершины 1. Списки смежности:

1: 2, 3
2: 1, 4
3: 1, 4
4: 2, 3

Как идёт обход:

  1. Из очереди берём 1. Вызывается process_vertex_early(1), затем process_edge(1,2) и process_edge(1,3), потом process_vertex_late(1).
  2. Берём 2. Вызывается process_vertex_early(2). Сосед 1 уже обработан, поэтому ребро (2,1) пропускается. Для соседа 4 вызывается process_edge(2,4).
  3. Берём 3. Аналогично, ребро (3,1) пропускается, вызывается process_edge(3,4).
  4. Берём 4. Оба соседа (2 и 3) уже обработаны, рёбер не вызывается.

Вывод программы с функциями из листинга 7.11:

processed vertex 1
processed edge (1,2)
processed edge (1,3)
processed vertex 2
processed edge (2,4)
processed vertex 3
processed edge (3,4)
processed vertex 4

Каждая вершина и каждое ребро напечатаны по одному разу. Если вместо этого использовать process_edge() из листинга 7.12, то в конце nedges будет равно 4.

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

Источник

С. Скиена, Алгоритмы. Руководство по разработке, гл. 7, п. 7.6.1, листинги 7.10-7.12.