Algoritmo para verificar se grafo orientado é fortemente ligado

StackOverflow https://stackoverflow.com/questions/1434787

Pergunta

Eu preciso verificar se um grafo direcionado é fortemente ligado , ou, em outras palavras, se todos os nós pode ser alcançado por qualquer outro nó (não necessariamente através de borda direta).

Uma maneira de fazer isso é executando um DFS e BFS em cada nó e veja todos os outros ainda são acessíveis.

Existe uma abordagem melhor para fazer isso?

Foi útil?

Solução

componentes fortemente conectados

de Tarjan algoritmo (ou variação de Gabow) vai, naturalmente bastar; se há apenas um componente fortemente conectado, então o gráfico está fortemente ligado.

Ambos são tempo linear.

Tal como acontece com uma profundidade normal de primeira pesquisa, você acompanhar o status de cada nó: nova, visto, mas ainda em aberto (que é na pilha de chamadas), e visto e acabado. Além disso, você armazenar a profundidade quando chegou pela primeira vez um nó, e o menor tal profundidade que é acessível a partir do nó (você sabe que isso depois de terminar um nó). Um nó é a raiz de um componente fortemente ligado se o menor profundidade acessível é igual a sua própria profundidade. Isso funciona mesmo se a profundidade pelo qual você chegar a um nó da raiz não é o mínimo possível.

Para verificar apenas para se todo o gráfico é um único SCC, iniciar as dfs de qualquer único nó, e quando tiver terminado, se o menor profundidade acessível é 0, e cada nó foi visitado, em seguida, todo o gráfico é fortemente ligado.

Outras dicas

Considere o seguinte algoritmo.

  1. Iniciar em um v vértice aleatório do G gráfico, e executar um DFS(G, v).

    • Se DFS(G, v) não conseguir chegar a todos os outros vértices na G gráfico, então há alguma u vértice, de tal forma que não há um caminho dirigido de v para u, e assim G é não fortemente ligado .

    • Se ele faz chegar a cada vértice, então existe um caminho dirigido de v para todos os outros vértices na G gráfico.

  2. Inverta a direcção de todas as bordas do gráfico dirigido G .

  3. Novamente executar um DFS a partir de v.

    • Se o DFS não conseguir chegar a cada vértice, então há alguma u vértice, de tal forma que no gráfico originais que não há é dirigida caminho de u para v.

    • Por outro lado, se ele chegar a cada vértice, então no gráfico originais existe um caminho dirigido a partir de cada vértice u para v .

Assim, se G "passa" tanto DFSS, é fortemente conectado. Além disso, desde a DFS é executado em tempo O(n + m), este algoritmo é executado em tempo O(2(n + m)) = O(n + m), uma vez que exige 2 DFS traversals.

Para verificar se cada nó tem dois caminhos de e para todos os outros nós em um determinado gráfico:

1. DFS / BFS de todos os nós:

Tarjan é algoritmo supõe cada nó tem um d[i] profundidade. Inicialmente, a raiz tem a menor profundidade. E fazemos as pós-ordem DFS atualizações d[i] = min(d[j]) para qualquer j vizinho de i. Na verdade BFS também funciona bem com o d[i] = min(d[j]) regra redução aqui. 

function dfs(i)
    d[i] = i
    mark i as visited
    for each neighbor j of i: 
        if j is not visited then dfs(j)
        d[i] = min(d[i], d[j])

Se houver um encaminhamento caminho de u para v, d[u] <= d[v] então. No SCC, d[v] <= d[u] <= d[v], assim, todos os nós no SCC terá a mesma profundidade. Para saber se um gráfico é um SCC, vamos verificar se todos os nós têm a mesma d[i].

2. Dois DFS / BFS do único nó:

É uma versão simplificada do de Kosaraju algoritmo . A partir da raiz, vamos verificar se cada nó pode ser alcançado pelo DFS / BFS. Em seguida, inverter o sentido de cada borda. Nós verificamos se cada nó pode ser alcançado a partir da mesma raiz novamente. Consulte C ++ código .

Você pode calcular a All-Pairs Shortest Path e ver se algum é infinito .

Algoritmo de Tarjan já foi mencionado. Mas eu geralmente encontrar Algoritmo de Kosaraju mais fácil de seguir mesmo que ele precisa de duas travessias do gráfico . IIRC, também é muito bem explicado em CLRS. 

test-connected(G)
{
    choose a vertex x
    make a list L of vertices reachable from x,
    and another list K of vertices to be explored.
    initially, L = K = x.

    while K is nonempty
    find and remove some vertex y in K
    for each edge (y, z)
    if (z is not in L)
    add z to both L and K

    if L has fewer than n items
    return disconnected
    else return connected
}

Uma maneira de fazer isso seria para gerar o Laplacian matriz para o gráfico, em seguida, calcular os valores próprios, e, finalmente, contar o número de zeros. O gráfico é fortemente conexão se existe apenas um zero valor próprio.

Nota:. Preste atenção ao método ligeiramente diferente para criar a matriz Laplacian para grafos dirigidos

Você pode usar o DFS da Kosaraju algoritmo simples baseado que faz duas travessias DFS de gráfico:

A idéia é, se cada nó pode ser alcançado a partir de um vértice v, e cada nó pode atingir v, então o gráfico está fortemente ligado. No passo 2 do algoritmo, vamos verificar se todos os vértices são acessíveis a partir de v. No passo 4, vamos verificar se todos os vértices pode chegar v (no gráfico invertida, se todos os vértices são acessíveis a partir de v, então todos os vértices pode chegar v no original gráfico).

Algoritmo: 1) Inicializar todos os vértices como não visitados.

2) Fazer um percurso DFS de gráfico a partir de qualquer arbitrária vértice v. Se DFS travessia não visita todos os vértices, em seguida, retornar falso.

3) Reverso todos os arcos (ou encontrar transposição ou reverter do gráfico)

4) Mark todos os vértices como não-visitados no gráfico revertida.

5) fazer um percurso DFS de gráfico reversa a partir de mesmo vértice v (mesmo que no passo 2). Se DFS travessia não visita todos os vértices, em seguida, retornar falso. Caso contrário, retornará true.

Tempo Complexidade:. Complexidade Tempo de execução acima referido é o mesmo como busca em profundidade, que é S (V + E), se o gráfico está representada utilizando representação lista adjacência

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top