grafos

Disciplina: Grafos
Semestre: 2017/2
Curso: Ciência da Computação
Professor: Max Pereira
Universidade do Sul de Santa Catarina (UNISUL)

Sumário

- Trabalho 1
- Trabalho 2
- Trabalho 3

---

Trabalho 1

Implementar as seguintes representações de grafos:

• Listas de arestas
• Listas de adjacência
• Matriz de adjacência
• Matriz de incidência

Entrada:

• Tipo de grafo: não-orientado ou orientado
• Valorado (s/n) – somente arestas
• Conjunto V
• Conjunto E

Saída:

• As três formas de representação

Trabalho 2

Implementar o algoritmo de Dijkstra:

Entrada:

• Tipo de grafo: não-orientado ou orientado
• Valorado - somente arestas
• Conjunto V
• Conjunto E
• Vértice inicial (origem)

Saída:

• As distâncias e os caminhos entre o vértice de origem e os demais vértices

Trabalho 3

Resolução do problema da árvore geradora mínima:
Implementar os dois algoritmos: Kruskal e Prim-Jarnik

Entrada:

• Tipo de grafo: não-orientado
• Valorado - somente arestas
• Conjunto V
• Conjunto E

Saída:

• As arestas do subgrafo (árvore geradora mínima) e o custo.