Ois,
Vitor, muito obrigado por levantar essa questão no fórum!
Tive um leve problema ao testar meu EP por conta do cloneDigraph.
Foi necessário arrumar o comportamento da minha cloneDigraph pra coisas funcionarem corretamente.
Opsss.
Desculpem.
A sua função estava funcionando corretamente!
A especificação que dei de cloneDigraph()
foi despretensiosa.
A sua cloneDigraph()
estava melhor que a minha!
Eu deveria ter feito como você e o algs4 e retornar um clone da representação de G
.
Isso parece ser mais apropriado.
A minha cloneDigraph()
clonava o digrafo, não sua representação.
Algumas funções que têm sido pedidas a vocês não tem resultado único.
O EP14 fala de uma representação topológica de G
.
A representação obtida depende da representação do digrafo e da maneira que fazemos a busca DFS
.
A propósito, só para insistir, esse negócio de representação topológica não existe, Ok?!
Foi apenas um nome que por falta de criativiade inventei para chamar a bagaça.
Vou aproveitar a oportunidade e me estender um pouco negócio de digrafos e suas represetações.
Um digrafo (grafo = digrafo simétrico) é um objeto combinátorio: vértice + arcos (arestas) + relação de adjacência.
Um digrafo pode ser representado no computador de várias formas, inclusive vetor de listas de adjacência que temos usado.
Um mesmo digrafo tem várias representações.
Embaralhar a linhas do arquivo tinyDG.txt
correspondente aos arcos alteram a representação do digrafo.
Todas são representações do mesmo digrafo.
Um coisa bacana dos algoritmos que temos visto é que a representação do digrafo é irrelevante.
Inclusive temos construído florestas DFS
de maneiras arbitrárias.
O trecho de código abaixo é conveniente para explorarmos um digrafo em ordem DFS
, mas é arbitrário:
for (int v = 0; v < G.V(); v++) { if (!marked[v]) { dfs(G, v); } }
Por alguma razão misteriosa poderíamos construir as florestas DFS
de outra maneira:
for (int v = G.V()-1; v >= 0; v--) { if (!marked[v]) { dfs(G, v); } }
É muito bacana que independentemente da representação do digrafo e independentemente da maneira que que fazemos a busca DFS
(independentemente da floresta DFS
) as funções que vimos (e uma infinidade que não vimos) fazemo o seu serviço com perfeição encontrando:
- um caminho até um dado vértice
- o corte separando dois vértices
- uma ordenação topológica;
- um ciclo;
- uma bipartição;
- um ciclo ímpar;
- as componentes conexas de um grafo;
- as componentes fortes de um digrafo;
- ...
Certamente há problemas em que a representação do (di)grafo e a maneira que o exploramos faz diferença.
Esse foram os meus dois centevas.
Novamente, Vitor, muito obrigado por compartilhar as suas observações.