DFS, ordenação topológica, conexão forte

Questões-guia:

1. Qual a explicação que Cormen dá para a BFS ser single-source enquanto que a DFS é multiple-source?  Você concorda com ela?
2. Por que Cormen exemplifica BFS em grafos não orientados, e DFS em grafos orientados?  Em LEMON, dá pra rodar BFS e DFS em quais tipos de grafos?
3. Quais são as saídas mais importantes de uma DFS?
4. Por que o código da DFS é dividido em duas funções, enquanto que o da BFS fica em uma só função?
5. O que é um DAG?
6. O que é ordenação topológica e como ela pode ser resolvida por DFS?
7. O que são componentes fortemente conexas?  Como diferem das componentes conexas que vimos anteriormente?
8. Se G é um grafo orientado, o que é G^SCC?  Que propriedade interessante tem G^SCC?
9. Como obter uma ordenação topológica em G^SCC a partir de uma DFS em G?
10. Se G é um grafo orientado, o que é o grafo G^T?  Como se relacionam G^SCC e (G^T)^SCC?

Exercícios:

1. Rode uma DFS da biblioteca LEMON no grafo usado como exemplo na Figura 22.4 do Cormen.  Quantas linhas deu seu código?  Deu a mesma busca do livro?
2. Resolva o Exercício 22.4-1 com a biblioteca LEMON.  Dica: use a class DfsVisit em lugar da Dfs normal.
3. Implemente o algoritmo para componentes fortemente conexas da Seção 22.5 do Cormen usando LEMON.  Teste no grafo da Figura 22.9.  Dica: além da DfsVisit, use o adaptador de grafos que calcula G^T e controle fino de DFS com os métodos init, addSource e start.