Teoria de Grafos

Projeto contendo a implementação dos exercícios recebidos em aula.

Representações

• Lista de Arestas
• Lista de Adjacência
• Matriz de Incidência
• Matriz de Adjacência

Tipos de grafo

• Valorado ou não valorado
• Direcionado ou dígrafo

Algoritmos para calcular o menor caminho

• Floyd-Warshall
• Dijkstra
• Bellman-Ford

Centro do Grafo

• Utilizando o algoritmo Floyd-Warshall

Árvore de Cobertura Mínima

• Kruskal

Busca em Profundidade (DFS)

• Aplicado a coloração.

Como utilizar

É necessário inserir a quantidade de vértices do grafo, assim como, o conjunto de arestas e seu respectivo valor.

Um grafo é representado da seguinte maneira:

(1,2,2) , (1,5,10), (2,3,3), (2,4,7), (3,4,4), (5,3,8), (5,4,5)

Sendo:

• Início da aresta.
• Destino da aresta.
• Valor/Custo da aresta. Caso não for um grafo valorado, aceita-se o valor 1 para quantificar uma aresta.