Sumários
Lab 10
10 maio 2012, 14:00 • Margarida Silveira
Realização do 10º trabalho de laboratório sobre procura em grafos. Os algoritmos de procura em profundidade (DFS) e procura em largura (BFS).
Grafos - III
10 maio 2012, 10:00 • José Teixeira de Sousa
- Procura em profundidade - DFS
- Exemplo de execução
- Implementação para matrizes de adjacências e listas de adjacências
- Comparação
- Propriedades
- Procura em largura - BFS
- Implementação para matrizes de adjacências
- Exemplo de execução
- Propriedades
- Implementação alternativas para matrizes de adjacências
- Procura generalizada em grafos
- Descrição
- Implementação
- Propriedades
- Árvores mínimas de suporte - MST
- Representação e implementação para grafos ponderados
- Propriedades das MST's - Exemplos
Grafos - II
8 maio 2012, 10:30 • José Teixeira de Sousa
- Representação de um grafo
- Listas de adjacências
- Implementação da estrutura abstracta de dados
- Comparação das representações alternativas
- Vantagens e inconvenientes das matrizes de adjacências
- Vantagens e inconvenientes das listas de adjacências
- Variantes e extensões
- Grafos direccionados, ponderados e redes
- Outras representações
- Comparação das representações alternativas
- Memória e tempo de execução
- Procura em grafos
- Analogia com a exploração de labirintos
- Estratégia de Tremaux
- Procura em profundidade - DFS
- Exemplo de execução