Нахождение сильно связанных компонентов в графе в одной DFS

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

  1. вызвать DFS(G), чтобы вычислить время окончания f [v] для каждой вершины v, отсортировать вершины G в порядке убывания времени их окончания;

  2. вычислить транспонирование GT из G;

  3. Выполните еще одну DFS на G, на этот раз в главном цикле for мы проходим вершины G в порядке убывания f[v];

  4. выведите вершины каждого дерева в лесу DFS (образованном вторым DFS) как отдельный сильно связанный компонент.

,

Но мне было интересно, можно ли найти все сильно связанные компоненты только в одной DFS.

Любая помощь в этом отношении будет принята с благодарностью.

Источник

2 ответа

Решение

Посмотрите, Руководство по разработке алгоритмов Стивена Скиены. Он рассчитывает SCC в одной DFS. Он основан на концепции самой старой достижимой вершины.

Инициализируйте каждую вершину достижимой вершины и SCComponent# для себя в начале.

low[i] = i;
scc[i] = -1;

Сделайте DFS на орграфе, вас интересуют только задние и поперечные ребра, потому что эти два ребра сообщат вам, если вы столкнулись с задним ребром и вводите 1 компонент из другого.

  int edge_classification(int x, int y)
  {
    if (parent[y] == x) return(TREE);
    if (discovered[y] && !processed[y]) return(BACK);
    if (processed[y] && (entry_time[y]>entry_time[x])) return(FORWARD);
    if (processed[y] && (entry_time[y]<entry_time[x])) return(CROSS);
     printf("Warning: unclassified edge (%d,%d)\n",x,y);
  }

Поэтому, когда вы сталкиваетесь с этими ребрами, вы устанавливаете достижимую вершину [] рекурсивно, основываясь на времени входа. if (class == BACK) { if (entry_time[y]

if (class == CROSS) 
{
            if (scc[y] == -1)  /* component not yet assigned */
                    if (entry_time[y] < entry_time[ low[x] ] )
                            low[x] = y;
}

Новый сильно связный компонент обнаруживается всякий раз, когда самой нижней достижимой вершиной из вершины 'v' является сама (цикл может сказать, a->b->c->a, самая низкая достижимая вершина a есть a).

process_vertex_early(int v)
{
    push(&active,v);
}

После того, как DFS для вершины завершена (DFS для ее соседей также была бы завершена), проверьте для нее самую низкую достижимую вершину:

if (low[v] == v) 
{     /* edge (parent[v],v) cuts off scc */
          pop_component(v);
}

if (entry_time[low[v]] < entry_time[low[parent[v]]])
          low[parent[v]] = low[v];

pop_component (...) просто извлекается из стека, пока не будет найден этот компонент. Если сканируется a-> b-> c-> a, в стеке будет всплывающее окно (внизу)->b->c(вверху).. до тех пор, пока не будет замечена вершина 'a'. Вы получаете SCC для 'a'.. и аналогичным образом вы получаете все подключенные компоненты в одной DFS.

Источник

Я нашел это на странице Википедии для Сильно подключенного компонента:

Алгоритм Косараю, алгоритм Тарьяна и алгоритм сильных компонентов на основе пути эффективно вычисляют сильно связанные компоненты ориентированного графа, но на практике алгоритм Тарьяна и алгоритм на основе путей предпочтительнее, поскольку для них требуется только один поиск в глубину, а не два.

Я думаю, что это вполне отвечает на ваш вопрос:)

Источник
Другие вопросы по тегам