3

Olá, gostaria de uma ajuda para fazer uma busca em um grafo e verificar se ele satisfaz o teorema de euler.

O teorema diz: "Um grafo conexo conterá um ciclo de Euler se, e somente se, cada um dos vértices tiver um número par de arestas incidindo sobre ele."

Então o problema se resume em descobrir o grau de cada um dos vértices do meu grafo, e se ele é conexo.

Pensei em representar meu grafo através de uma lista de adjacência, pois como cada vetor vai ter a lista de vizinhos, basta pedir seu tamanho menos um e obtenho o grau do vértice. Para descobrir se é conexo pensei em utilizar uma DFS, pois assim posso verificar tanto quanto possível cada um dos meus vizinhos no grafo.

De quais outras formas posso otimizar essa minha sugestão de solução?

3
  • 1
    Qual é o tamanho do grafo no caso médio? E no pior caso que você está disposto a tratar? Quais linguagens de programação te interessam ou não? Commented 24/08/2016 às 16:34
  • Victor, não tenho um tamanho definido. Mas se fosse para grafos pequenos, até mil vértices por exemplo, minha sugestão é boa? Em que situação minha sugestão vai ser ruim? Eu interessado em fazer isso em C++. Commented 24/08/2016 às 16:50
  • Pra mim descobrir se minha sugestão é boa ou não, teria de fazer uma análise de complexidade de algoritmo, correto? Commented 24/08/2016 às 16:56

1 Resposta 1

3

Para determinar se o grafo é conexo, a melhor abordagem provavelmente é a busca em largura ou em profundidade. (Referência)

Para contar o grau de cada vértice, você pode usar lista de adjacências ou matriz de adjacências. Ambas as abordagens consomem memória O(|v|^2) no pior caso.

Para determinar se dois vértices são vizinhos, você tem que percorrer a lista de adjacências de um deles e procurar sequencialmente o outro vértice desejado lá, o que é razoavelmente lento. Com matriz de adjacências, isso pode ser feito em tempo constante.

Para computar o grau de um vértice, ou você percorre a lista de adjacências inteira, ou conta o número de elementos na linha. Ambas as abordagens têm tempo proporcional a O(|v|) para cada vértice, de forma que será O(v^2) se aplicado ao grafo inteiro.

Para grafos esparsos onde o número de arestas é proporcional ao número de vértices (ou seja, |e| <= k|v|, para algum k constante e pequeno), que significa que há um limite fixo de arestas incidentes em um vértice, a melhor abordagem é a lista de adjacências, pois neste caso, essas listas serão curtas. Para grafos densos, as listas ocuparão mais memória do que a matriz de adjacência correspondente, e para descobrir se dois vértices a e b são vizinhos, você terá que percorrer a lista de adjacências de um deles, elemento por elemento, fazendo uma busca sequencial, o que é bem lento.

Como você quer grafos com até 1000 vértices, a matriz de adjacência terá 1.000.000 de entradas no pior caso. Considerando que você use um char[] no C++ e que sizeof char é 1, isso dará pouco menos de 1 Mb de memória, o que não é lá muita coisa. Assim sendo, matriz de adjacências parece ser uma abordagem bem melhor do que lista de adjacências.

Há ainda uma otimização importante, que depende de como o grafo é construído. Supondo que você tenha em algum lugar uma lista de arestas ou um gerador de arestas, convém manter em algum lugar, um array contendo o grau de cada vértice, de forma que sempre que uma aresta é declarada, você incrementa 1 em ambas as posições correspondentes do array. Ao terminar, você verifica se o array contém algum elemento ímpar ou o número zero. Se conter ímpar, então ele não é euleriano. Se houver zero, então ele não é conexo (a menos que o grafo consista de um único vértice isolado). Se todos os elementos forem pares e nenhum for zero, faça a DFS ou BFS. Com esta abordagem, é possível computar o grau de todos os vértices em tempo O(|v| + |e|).

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 .