Ola, boa noite
Na função addEdge, devemos conferir se o arco v-w já existe?
Ou podemos assumir que nenhum arco será inserido duas vezes?
Considerando que é um problema registrar o mesmo arco duas vezes..
Isso é um problema, certo ? :|
No meio dos testes me deparei com a resposta da minha pergunta 'o'
No exemplo
2 vertices, 4 edges
0: 1 1 1
1: 0
Há 3 arcos iguais, então acredito que a resposta para minhas perguntas seja não hehe
Olá, estou com uma dúvida sobre o mesmo assunto.
O ep13 contém a seguinte frase comentada no início do arquivo digraph.c:
"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."
Como são permitidos laços paralelos, e os vetores de adjacência guardam bags com int, imagino que o consumo de tempo esteja limitado a ser, no melhor caso, proporcional ao número de arcos, não sendo possível que seja proporcional ao número de vértices, a menos que a bag guarde uma estrutura que diz qual o vértice adjacente e quantos arcos paralelos apontam para esse vértice (nesse caso a operação add() não seria O(1), pois teria que verificar se já existe um arco paralelo ao que está sendo adicionado).
É isso mesmo ou interpretei algo errado?
Acho que os arcos repetidos importam. Acho que é do cliente lidar com esses casos se ele não quiser considerar arcos repetidos.
Fiz um EP com o Yoshi que era o page rank, que usava um grafo pra dar pesos para sites de acordo com a importância, analisando os links que levavam pra esse site ( algoritmo bem legal!). Nesse caso cada site é um node e os links são arcos, e faz diferença se um site tem um ou dez links pra ele mesmo.
Olá,
Complementando o que o Pedro disse, acho que para essa implementação, não devemos nos preocupar com arcos repetidos.
A própria implementação apresentada como exemplo correto de execução não trata isso.
Ademais, nem a implementação de Digraph nem a de Bag do algs4 se preocupam com esse detalhe.
Dito isso, acho muito provável que não devemos fazer um tratamento para arestas repetidas.
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).