Как доказать линейный алгоритм, который идентифицирует все циклы и длину в графе, где каждая вершина имеет ровно одно исходящее ребро - PullRequest
Новая
       42

Как доказать линейный алгоритм, который идентифицирует все циклы и длину в графе, где каждая вершина имеет ровно одно исходящее ребро

0 голосов
/ 29 января 2020

Рассмотрим ориентированный граф на n вершинах, где каждая вершина имеет ровно одно исходящее ребро. Этот граф состоит из набора циклов, а также дополнительных вершин, которые имеют пути к циклам, которые мы называем ветвями. Опишите алгоритм линейного времени, который идентифицирует все циклы и вычисляет продолжительность каждого цикла. Можно предположить, что входные данные задаются в виде массива A, где A [i] является соседом i, поэтому у графа есть ребро (i, A [i]).

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

1 Ответ

1 голос
/ 29 января 2020

Если вам разрешено использовать дополнительную память, алгоритм в Python будет выглядеть следующим образом. 

colors = [0] ** N; # initialize N element array withe values of zero (not seen)
for i in range(N):
    v = i # current vertex
    if colors[v] != 0: continue # already seen
    colors[v] = 1 # seen
    v = A[v] # move to neighbor
    while colors[v] == 0:
       colors[v] = 1
       v = A[v] # move to neighbor
    # we have reached previously seen node; this is the start node of a cycle
    colors[v] = 2 # mark the start of a cycle
    cycle_len = 1
    v = A[v] # move to neighbor
    while colors[v] == 1:
       cycle_len += 1
       v = A[v] # move to neighbor
   print("got a cycle with length =", cycle_len)

Основная идея c состоит в том, чтобы использовать три цвета для разной маркировки узлов, которые уже были посещены и узлы, которые являются отправными точками циклов; очевидно, один узел может принадлежать только одному циклу.

Алгоритм является линейным, поскольку внутренний while l oop выполняется только для узлов, которые ранее не были видны. Узлы, которые мы уже видели, пропускаются. В худшем случае оба внутренних цикла while полностью выполняются, но 2 * N по-прежнему равно O (N).

Использование хэш-карты не соответствует требованиям, поскольку сложность времени наихудшего случая для хеш-карт не линейно.

...