Ciclos em um Gráfico Não Dirigido

Dado um grafo não direcionado G = ( V , E ) com n vértices (| V | = n ), como você encontra se contém um ciclo em O ( n )?

   

    Eu acho que a primeira pesquisa de profundidade resolve isso. Se uma borda inexplorada levar a um nó visitado antes, o gráfico conterá um ciclo. Essa condição também faz com que seja O (n), já que você pode explorar no máximo n arestas sem defini-lo como verdadeiro ou ficar sem arestas inexploradas.

    Na verdade, a profundidade em primeiro lugar (ou, na verdade, a largura em primeiro lugar) não é suficiente. Você precisa de um algoritmo visualmente mais complexo.

    Por exemplo, suponha que haja um gráfico com nós {a, b, c, d} e arestas {(a, b), (b, c), (b, d), (d, c)} onde uma aresta (x , y) é uma aresta de x para y. (parece algo assim, com todas as bordas direcionadas para baixo).

    (a) | | (b) / \ (d) | | | \ / (c) 

    Então, fazer a primeira pesquisa de profundidade pode visitar o nó (a), depois (b), depois (c), depois voltar para (b), depois visitar (d) e finalmente visitar (c) novamente e concluir que há um ciclo – quando não há. Uma coisa semelhante acontece com amplitude primeiro.

    O que você precisa fazer é acompanhar quais nós estão no meio da visita. No exemplo acima, quando o algoritmo atinge (d), ele terminou de visitar (c), mas não (a) ou (b). Então revisitar um nó acabado é bom, mas visitar um nó inacabado significa que você tem um ciclo. A maneira usual de fazer isso é colorir cada nó branco (ainda não visitado), cinza (visitando descendentes) ou preto (visitas concluídas).

    aqui está algum pseudo código!

     define visit(node n): if n.colour == grey: //if we're still visiting this node or its descendants throw exception("Cycle found") n.colour = grey //to indicate this node is being visited for node child in n.children(): if child.colour == white: //if the child is unexplored visit(child) n.colour = black //to show we're done visiting this node return 

    então a visita em execução (root_node) lançará uma exceção se e somente se houver um ciclo (inicialmente todos os nós devem ser brancos).

    Um grafo G não conectado que não tem ciclos é uma tree! Qualquer tree tem exatamente n – 1 arestas, então podemos simplesmente percorrer a lista de arestas do gráfico e contar as arestas. Se contarmos n – 1 arestas, então retornamos “sim”, mas se atingirmos a enésima borda, retornaremos “não”. Isso leva O (n) tempo porque nós olhamos no máximo n arestas.

    Mas se o gráfico não estiver conectado, teremos que usar o DFS. Podemos atravessar as arestas e se quaisquer arestas inexploradas conduzirem ao vértice visitado, então ele terá ciclo.

    Você pode resolvê-lo usando o DFS. Complexidade de tempo: O (n)

    A essência do algoritmo é que, se um componente / gráfico conectado NÃO contiver um CICLO, ele será sempre uma ÁRVORE. Veja aqui para comprovar

    Vamos supor que o gráfico não tenha ciclo, ou seja, é uma tree. E se olharmos para uma tree, cada aresta de um nó:

    1.Apenas alcança seu único pai, que é um nível acima dele.

    2.ou alcança seus filhos, que estão um nível abaixo dele.

    Portanto, se um nó tiver qualquer outra borda que não esteja entre as duas descritas acima, obviamente conectará o nó a um de seus ancestrais, além de seu pai. Isso formará um ciclo.

    Agora que os fatos são claros, tudo o que você precisa fazer é executar um DFS para o gráfico (considerando que seu gráfico está conectado, caso contrário, para todos os vértices não visitados) e SE encontrar um vizinho do nó VISITED e NOT pai, então meu amigo, há um CICLO no gráfico e você é FEITO.

    Você pode acompanhar o pai simplesmente passando o pai como parâmetro ao fazer o DFS para seus vizinhos. E como você só precisa examinar n arestas no máximo, a complexidade de tempo será O (n).

    Espero que a resposta tenha ajudado.

    A propósito, se você souber que está conectado, simplesmente é uma tree (portanto, sem ciclos) se e somente se |E|=|V|-1 . Claro que não é uma pequena quantidade de informação 🙂

    A resposta é, na verdade, a primeira pesquisa em profundidade (ou a primeira pesquisa aprofundada, isso realmente não importa). Os detalhes estão na análise.

    Agora, quão rápido é o algoritmo?

    Primeiro, imagine o gráfico sem ciclos. O número de arestas é então O (V), o gráfico é uma floresta, meta alcançada.

    Agora, imagine o gráfico tem ciclos, e seu algoritmo de busca terminará e reportará sucesso no primeiro deles. O gráfico não é direcionado e, portanto, quando o algoritmo inspeciona uma aresta, há apenas duas possibilidades: ou ele visitou a outra extremidade da aresta, ou então, essa aresta fecha um círculo. E uma vez que ele vê o outro vértice da borda, esse vértice é “inspecionado”, portanto, há apenas O (V) dessas operações. O segundo caso será alcançado apenas uma vez durante a execução do algoritmo.

    Eu acredito que a suposição de que o gráfico está conectado pode ser um punhado. assim, você pode usar a prova mostrada acima, que o tempo de execução é O (| V |). se não, então | E |> | V |. lembrete: o tempo de execução do DFS é O (| V | + | E |) .

    Aqui está o código que escrevi em C com base no DFS para descobrir se um determinado gráfico está conectado / cíclico ou não. com alguma amostra de saída no final. Espero que seja útil 🙂

     #include #include /****Global Variables****/ int A[20][20],visited[20],v=0,count=0,n; int seq[20],s=0,connected=1,acyclic=1; /****DFS Function Declaration****/ void DFS(); /****DFSearch Function Declaration****/ void DFSearch(int cur); /****Main Function****/ int main() { int i,j; printf("\nEnter no of Vertices: "); scanf("%d",&n); printf("\nEnter the Adjacency Matrix(1/0):\n"); for(i=1;i< =n;i++) for(j=1;j<=n;j++) scanf("%d",&A[i][j]); printf("\nThe Depth First Search Traversal:\n"); DFS(); for(i=1;i<=n;i++) printf("%c,%d\t",'a'+seq[i]-1,i); if(connected && acyclic) printf("\n\nIt is a Connected, Acyclic Graph!"); if(!connected && acyclic) printf("\n\nIt is a Not-Connected, Acyclic Graph!"); if(connected && !acyclic) printf("\n\nGraph is a Connected, Cyclic Graph!"); if(!connected && !acyclic) printf("\n\nIt is a Not-Connected, Cyclic Graph!"); printf("\n\n"); return 0; } /****DFS Function Definition****/ void DFS() { int i; for(i=1;i<=n;i++) if(!visited[i]) { if(i>1) connected=0; DFSearch(i); } } /****DFSearch Function Definition****/ void DFSearch(int cur) { int i,j; visited[cur]=++count; seq[count]=cur; for(i=1;i 

    / * Saída da amostra:

     majid@majid-K53SC:~/Desktop$ gcc BFS.c majid@majid-K53SC:~/Desktop$ ./a.out ************************************ Enter no of Vertices: 10 Enter the Adjacency Matrix(1/0): 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 The Depdth First Search Traversal: a,1 c,2 d,3 f,4 b,5 e,6 g,7 h,8 i,9 j,10 It is a Not-Connected, Cyclic Graph! majid@majid-K53SC:~/Desktop$ ./a.out ************************************ Enter no of Vertices: 4 Enter the Adjacency Matrix(1/0): 0 0 1 1 0 0 1 0 1 1 0 0 0 0 0 1 The Depth First Search Traversal: a,1 c,2 b,3 d,4 It is a Connected, Acyclic Graph! majid@majid-K53SC:~/Desktop$ ./a.out ************************************ Enter no of Vertices: 5 Enter the Adjacency Matrix(1/0): 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 The Depth First Search Traversal: a,1 d,2 b,3 c,4 e,5 It is a Not-Connected, Acyclic Graph! */ 

    Um simples DFS faz o trabalho de verificar se o dado gráfico não direcionado tem um ciclo ou não.

    Aqui está o código C ++ para o mesmo.

    A ideia usada no código acima é:

    Se um nó que já é descoberto / visitado for encontrado novamente e não for o nó pai, então temos um ciclo.

    Isso também pode ser explicado abaixo (mencionado por @ Rafał Dowgird

    Se uma borda inexplorada levar a um nó visitado antes, o gráfico conterá um ciclo.

    Um gráfico não direcionado é acíclico (isto é, uma floresta) se um DFS não gerar bordas de volta. Como as arestas de retaguarda são aquelas arestas ( u , v ) conectando um vértice u a um ancestral v em uma tree em profundidade, então nenhuma retaguarda significa que há apenas arestas de trees, portanto não há nenhum ciclo. Então podemos simplesmente divertir o DFS. Se encontrar uma borda traseira, há um ciclo. A complexidade é O(V ) vez de O(E + V ) . Como se existe um back edge, ele deve ser encontrado antes de ver |V | arestas distintas. Isso ocorre porque em uma floresta acíclica (não direcionada), |E| ≤ |V | + 1 |E| ≤ |V | + 1 |E| ≤ |V | + 1 .

    Comecei a estudar charts recentemente. Eu escrevi um pedaço de código em java que poderia determinar se um gráfico tem ciclos. Eu usei o DFT para encontrar ciclos no gráfico. Em vez de recursion, usei uma pilha para percorrer o gráfico.

    Em um alto nível DFT usando uma pilha é feito nas etapas a seguir

    1. Visite um nó
    2. Se o nó não estiver na lista visitada, adicione-o à lista e empurre-o para o topo da pilha.
    3. Marque o nó no topo da pilha como o nó atual.
    4. Repita o procedimento acima para cada nó adjacente do nó atual
    5. Se todos os nós foram visitados, retire o nó atual da pilha

    Eu realizei um DFT de cada nó do Graph e durante o percurso, se eu encontrasse um vértice que eu visitei anteriormente, eu verifiquei se o vértice tinha uma profundidade de pilha maior que um. Também verifiquei se um nó tinha uma borda para si mesmo e se havia várias arestas entre os nós. A versão da pilha que eu escrevi originalmente não era muito elegante. Eu li o pseudo código de como isso poderia ser feito usando recursion e foi legal. Aqui está uma implementação de java. O array LinkedList representa um gráfico. com cada nó e seus vértices adjacentes denotados pelo índice da matriz e cada item respectivamente

     class GFG { Boolean isCyclic(int V, LinkedList[] alist) { List visited = new ArrayList(); for (int i = 0; i < V; i++) { if (!visited.contains(i)) { if (isCyclic(i, alist, visited, -1)) return true; } } return false; } Boolean isCyclic(int vertex, LinkedList[] alist, List visited, int parent) { visited.add(vertex); for (Iterator iterator = alist[vertex].iterator(); iterator.hasNext();) { int element = iterator.next(); if (!visited.contains(element)) { if (isCyclic(element, alist, visited, vertex)) return true; } else if (element != parent) return true; } return false; } 

    }

    Você pode usar biblioteca de charts de aumento e dependencies cíclicas . Tem a solução para encontrar ciclos com function back_edge .

    Como outros já mencionaram … Uma primeira pesquisa aprofundada irá resolvê-lo. Na profundidade geral, a primeira busca leva O (V + E), mas nesse caso você sabe que o gráfico tem no máximo O (V) arestas. Assim, você pode simplesmente executar um DFS e, quando vir uma nova borda, aumentar um contador. Quando o contador atingir V você não precisa continuar porque o gráfico tem certamente um ciclo. Obviamente, isso leva O (v).

    Eu acredito que usar o DFS corretamente também depende de como você vai representar seu gráfico no código. Por exemplo, suponha que você esteja usando listas adjacentes para acompanhar os nós vizinhos e seu gráfico tenha 2 vértices e apenas uma borda: V = {1,2} e E = {(1,2)}. Neste caso, a partir do vértice 1, o DFS marcará como VISITED e colocará 2 na fila. Depois disso, ele explodirá o vértice 2 e, como 1 é adjacente a 2, e 1 é VISITED, o DFS concluirá que há um ciclo (que está errado). Em outras palavras, em grafos não orientados (1,2) e (2,1) são a mesma borda e você deve codificar de uma maneira para o DFS não considerá-los diferentes arestas. Manter o nó pai para cada nó visitado ajudará a lidar com essa situação.

    Um gráfico sem direção sem ciclo tem | E | < | V | -1.

     public boolean hasCycle(Graph g) { int totalEdges = 0; for(Vertex v : g.getVertices()) { totalEdges += v.getNeighbors().size(); } return totalEdges/2 > g.getVertices().size - 1; }