3

Estou criando um algoritmo que identifica se um grafo contém ciclos excluído as fontes recursivamente, retornando o grafo para posterior verificação da quantidade de aresta, pra isso crie o seguinte código pra matrizes de adjacência:

Graph GRAPHisCycle( Graph F, vertex v) {
    while( v < F->V) {
        vertex w = 0;       
        while (w < F->V) {
            if( F->adj[v][w] == 1 && GRAPHoutdeg( F, v) > 0 && GRAPHindeg( F, v) == 0) {        
                GRAPHremoveA( F, v, w);
                GRAPHisCycle( F, v); 
             }
        ++w;
        }
    ++v;
    }
    return F;
}

GRAPHoutdeg e GRAPHindeg representam o grau de saída e entrada. Achei que esse código consome muito tempo. Não quero verificar ele por numeração topológica, aplicando uma DFS, queria rodar ele usando a DFS de outra maneira, sem essa verificação, tem como?

1
  • 2
    Sua implementação do algoritmo não parece eficiente. Porque realizar diversas recursões ? Você poderia armazenar uma lista com os nos de grau de entrada 0, ir removendo os nos dessa lista (e atribuindo a v) e depois de remover a aresta verificar se w deve entrar na lista dos nos com grau de entrada 0.
    – Felipe
    Commented 22/09/2017 às 1:34

1 Resposta 1

1

Para a busca em profundidade você pode usar a notação paretética, para ajudar a visualizar a lógica do algoritmo, quando visitamos um nó u, abrimos uma parenteses (u e quando a recursão returna até u, fechamos o parenteses u) assim, suponha que noss grafo visite os nós u->w->v, nossa notação ficaria (u (w (v v) w) u) indicando a ordem em que cada nó foi aberto (visitado pela primeira vez) e fechado (quando a recursão retorna até ele), fica fácil vizualisar um ciclo com essa notação, suponha que o ciclo ocorra com os vértices w->v->w->v->... nossa notação ficara (w (v (w (v..., ou seja, um dos nós do nosso ciclo foi visitado novamente antes de ser fechado, no algoritmo de BFS isso se traduz em visitar um nó cinza (aberto, mas ainda n fechado) temos então um algoritmo

  1. Marque todos os nós com a cor branca
  2. Escolha um nó para começar a busca, marque-o com cinza
  3. Faça a chamada recursiva para um dos nós vizinhos ao atual
  4. Quando a recursão retorna de um determinado nó, ou seja, quando a DFS em um nós termina e aquele nó é fechado, marque-o como preto
  5. Se você visitar um nó cinza, você encontrou um ciclo, pare o algoritmo

É possível provar que, se você visita um nó que está cinza, você encontrou um ciclo, ainda, nós que estejam brancos ou pretos não podem fazer parte de um ciclo (não foram visitados antes ou durante o ciclo no caso dos brancos e no caso dos pretos, a busca terminou sem encontrar um ciclo), assim, só nós que estejam cinzas podem fazer parte do ciclo (embora não necessariamente farão). Durante a busca em profundidade você tambêm pode armazenar a ordem em que os nós foram visitados para reconstruir o ciclo, eliminando os nós cinzas que não fazem parte do mesmo.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .