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

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

0 голосов
/ 12 июля 2020

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

В настоящее время он возвращает все вершины для каждого S CC.

Как можно изменить это, так что он возвращает все ребра для каждого, например, S CC

stack STACK
void DFS(int source) {
    visited[s]=true
    for all neighbours X of source that are not visited:
        DFS(X)
    STACK.push(source)
}

CLEAR ADJACENCY_LIST
for all edges e:
    first = one end point of e
    second = other end point of e
    ADJACENCY_LIST[second].push(first)
    
while STACK is not empty:
    source = STACK.top()
    STACK.pop()
    if source is visited :
        continue
    else :
        DFS(source)

. в этой Link тип возврата:

0 1 2

3

4

Я хочу, чтобы он также возвращал края между ними. Итак, для первого это будет:

(2,1), (1, 0), (0, 2)

null

null

Последние два равны нулю, потому что S CC - это просто отдельные узлы

...