Grafos

Estrutura básica do grafo:

A) Classe base Grafo com:

• Vetor de vértices
• Se o grafo é ponderado
• Se o grafo é direcionado

B) Classes derivadas:

• Grafo Matriz
• Grafo Lista

C) Cada classe derivada deve conter:

• Estrutura de arestas
• Inserção de vértices
• Inserção de arestas
• Verificar a existência e retornar o peso de uma arestas
• Retornar os vizinhos de um vértice
• Imprimir o grafo (console)

Busca

Dentro da classe pai:

Busca em largura:

• Não precisa ter um destino
• Retornar uma lista da ordem de visita dos vértices

Busca em profundidade:

• Não precisa ter um destino
• Retornar uma lista da ordem de visita dos vértices

Dijkstra:

• Não precisa ter um destino
• Retornar duas listas:
• Distância dos vértices para a origem
• Vértice anterior