BFS, distâncias

Questões-guia:

1. Em grafos, temos em geral dois parâmetros que medem o tamanho da entrada: V e E.  O que significa formalmente f(V,E) = O(g(V,E))?
2. Qual a diferença entre as definições de grafos em West e em Cormen?  LEMON é mais próximo de qual dos dois?
3. Quais as vantagens de desvantagens da representação por listas de adjacência, em relação a matrizes de adjacência?
4. Quais são as saídas mais importantes de uma BFS?
5. Como seria a tradução do algoritmo BFS(G,v) do Cormen (página 595) para LEMON?  O que você usaria para ENQUEUE e DEQUEUE?
6. O que é análise agregada?  Qual a complexidade de BFS em termos de V e E?
7. A árvore BFS de um grafo é única?  Se não for, dê exemplos.

Exercícios:

1. Modifique BFS para descobrir se um grafo é bipartido e, se não for, exibir um ciclo ímpar.
2. Como seria a adaptação de BFS para grafos com arestas múltiplas e laços?
3. Se fosse para imprimir um caminho mais curto de v para s, como você escreveria o algoritmo PRINT-PATH (página 601)?