Para determinar se o grafo é conexo, a melhor abordagem provavelmente é a busca em largura ou em profundidade. (Referência)(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 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 para cada vértice, de forma que será se aplicado ao grafo inteiro.
Para grafos esparsos onde o número de arestas é proporcional ao número de vértices (ou seja, , para algum 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 e 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 .