Olas,
Legal a discussão!
Seria legal se sempre fosse assim.
Aqui vão meus 2 centavos.
Na função addEdge, devemos conferir se o arco v-w já existe?
A sua preocupação é legítima.
No nosso caso, não precisamos nos preocupar com isso.
Dependendo da aplicação pode ser que arcos paralelos ou laços sejam inadmissíveis.
acho muito provável que não devemos fazer um tratamento para arestas repetidas.
Concordo.
Ou podemos assumir que nenhum arco será inserido duas vezes?
Não precisamos supor isso.
No nosso caso, não há nada errado em um termos dois arcos u-v ou v-v.
"Todas as operações consomen no pior caso tempo constante, exceto
iterar sobre os vértices adjacentes a um determinado vértice, cujo
consumo de tempo é proporcional ao número de tais vértices."
Isso que eu escrevi está errado.
É isso que escrever as coisas sem reler...
Cada chamada de adj() deve consumir tempo constante.
O consumo de tempo para percorrer/iterar sobre o vetor de adjacência de um vértice deve ser proporcional ao número de arcos com ponta inicial no vértice.
No consumo de tempo O(V + E) da DFS e da BFS o 'E' vem desse consumo de tempo.
Acho que é do cliente lidar com esses casos se ele não quiser considerar arcos repetidos.
Acho essa opção razoável.
Nos implementamos o Digraph.
O cliente é que decide se o digrafo deve ou não ter arcos repetidos ou laços.
O digrafo mediumDG.txt do algs4 tem arcos paralelos e laço:
% grep 45 mediumDG.txt 1 45 45 8 45 14 <<<<< 45 14 <<<<< 45 15 45 49 > grep 49 mediumDG.txt 1 49 15 49 29 49 45 49 49 34 49 22 49 49 <<<<<
No meio dos testes me deparei com a resposta da minha pergunta 'o'
Legal!
Tudo que vocês escreveram e o que eu escrevi não é fogo escrito na pedra.
As decisões de projeto dependem da aplicação.
Certamente há aplicações que não são admitidos arcos paralelos (dois ou mais arcos da forma v-w) ou laços (arcos da forma v-v).