Обходы графов

Обход в глубину

Сперва вспомним алгоритм обхода в глубину, который мы обсуждали на прошлом уроке. На каждом его шаге мы находимся в некоторой вершине графа и храним путь от начальной вершины до нас. Если мы не ходили в какую-то из соседних вершин, идём туда. В противном случае возвращаемся туда, откуда пришли. Основная часть этого алгоритма выражается, например, так:

path    = [start]
visited = set()
while path:
    current_place = path[-1]
    visited.add(current_place)
    if is_good(current_place): break
    
    to_visit = [n for n in neigbors(graph,current_place)
                  if  n not in visited]
    
    if to_visit: path.append(to_visit[0])
    else:        path.pop()

А теперь мы приведём альтернативную версию того же обхода, основанную на другой идеологии, которая имеет полезные обобщения.

Фронтовой подход

Любую связную компоненту графа можно обойти следующим методом: на каждом шаге храним фронт — множество соседей тех вершин, в которых мы уже были. Если фронт непуст, забираем из него любую вершину, а вместо неё добавляем всех её непосещённых соседей. Этот алгоритм выражается так:

front   = make_front([start])
visited = set()
while not is_empty(front):
    vertex = take_from(front)
    if vertex in visited: continue
    visited.add(vertex)
    if is_good(vertex): break
    
    to_visit = [n for n in neighbors(graph,vertex)
                  if  n not in visited]
    
    extend(front,to_visit)

Порядок обхода определяется конкретными реализациями функций make_front, take_from, extend и is_empty. Например, для

def make_front(list): return list
def take_from(front): return front.pop()
def extend(front,xs): front.extend(xs)
def is_empty(front):  return len(front) == 0

получается обход в глубину.

Обход в ширину

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

Навиная реализация выглядит так:

def make_front(list): return list
def take_from(front): return front.pop(0)
def extend(front,xs): front.extend(xs)
def is_empty(front):  return len(front) == 0

К сожалению, она страдает от очень неэффективной реализации take_from: удаление начального элемента массива требует копирования всей оставшейся части массива. Про эффективную реализацию обхода в ширину поговорим чуть позже, поскольку перед этим нужно сделать важную интерлюдию.

Абстрактные типы данных

То, что в прошлом разделе мы называли словом фронт, представляет собой пример абстрактного типа даннах. Абстрактный тип данных задаётся конструкторами и операциями (а также — свойствами, которыми эти операции должны обладать).

Конструкторы — это единственные способы создания представителей абстрактного типа данных. Все операции работают только с результатами конструкторов. Это соглашение обеспечивает независимость от внутреннего представления: если код, использущий абстрактный тип данных, уважает свойства этого абстрактного типа данных, то изменение реализаций конструкторов и операций не влияет на работоспособность кода.

В частности, если фронт хранит множество элементов фронта, take_from забирает один элемент из множества элементов фронта, а extend добавляет свой вход к множеству элементов фронта, то, независимо от того, как именно реализованы эти операции, фронтовой алгоритм обхода гарантирует полный обход конечной связной компоненты графа.

В заключение приведём полноценный пример абстрактного типа данных -- натуральные числа. Натуральные числа задаются одним конструктором

zero()

и двумя операциями

succ(n)
induct(base,transition)

Эти операции должны удовлетворять принципу Пеано-Ловера-Дедекинда: если a — элемент множества A, а функция f осуществляет отображение множества A в себя, то

induct(a,f)(zero())  == a
induct(a,f)(succ(n)) == f( induct(a,f)(n) )

причём для любой функции g, экстенсионально эквивалентной (то есть равной для всех допустимых значений аргумента) функции f, должны быть экстенсионально эквивалентны induct(a,f) и induct(a,g).

Один из способов реализации натуральных чисел таков:

def zero():  return 0
def succ(n): return n+1
def induct(b,t):
    def seq(n):
        if n == 0: return b
        return t(seq(n-1))
    return seq

Другой способ реализации таков:

def zero():  return []
def succ(n): return [n]
def induct(b,t):
    def seq(n):
        if not n: return b
        return t(seq(n[0]))
    return seq

А вот пример функции, работоспособность которой не зависит от того, какой из способов реализации выбран:

def to_int(n):
    return induct(0, lambda x: x+1)(n)

Подробнее про принцип индукции можно прочитать здесь.

Очередь

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

Циклическим массивом называется тройка \((s,x,y)\), где \(s\) — массив длины \(N\), а \(x,y\) — целые числа в пределах от \(0\) до \((s-1)\). Если \(x\leqslant y\), то рабочей частью циклического массива называется множество \({x,x+1,x+2,\ldots, y-1}\). Если \(x>y\), то рабочей частью называется множество \({x,x+1,x+2,\ldots,N-1,0,1,\ldots y-1}\).

Добавление единицы данных в циклический массив \((s,x,y)\) происходит так: в ячейку \(s[y]\) кладётся эта единица данных, затем \(y\) увеличивается на \(1\) по модулю \(N\).

Взятие единицы данных происходит из ячейки \(s[x]\). После взятия единицы данных число \(x\) увеличивается на \(1\) по модулю \(N\).

Задание

  1. По словесному описанию, приведённому выше, реализуйте циклический массив в виде набора из пяти функций:
# создаёт пустую очередь
def make_queue(capacity):  
    return ([None]*capacity, 0, 0)

# вычисляет размер рабочей части
def queue_size(q):
    pass  # заполните самостоятельно

# определяет, можно ли ещё добавить элементы
def queue_is_full(q):
    return len(q[0]) == queue_size(q) + 1

# добавляет элемент в очередь
def queue_push(q,x):
    pass  # заполните самостоятельно

# забирает элемент из очереди
def queue_pop(q):
    pass  # заполните самостоятельно

  1. Реализуйте обход в ширину при помощи очереди. А именно, в терминах функций из задачи 1 реализуйте функции make_front, take_from, extend и is_empty.

  2. Очередь из пункта 1 обладает незначительной проблемой: одну из ячеек массива нельзя использовать для хранения данных (поймите, почему!). Модифицируйте определение так, чтобы была возможность использовать весь массив.