O que é um Grafo?

Um grafo é uma estrutura de dados que modela um conjunto de coisas e as conexões entre elas. As coisas são chamadas de vértices (ou nós) e as conexões são chamadas de arestas.

Grafos estão em toda parte. Redes sociais são grafos (pessoas são vértices, amizades são arestas). Mapas rodoviários são grafos (interseções são vértices, ruas são arestas). A internet, árvores de dependência e mapas de jogos são todos grafos.

Neste curso, focamos em um grafo não direcionado: se uma aresta conecta u e v, então v também está conectado a u. Não há direção. Usaremos inteiros como as chaves dos vértices para manter as coisas simples.

Internamente, armazenaremos o grafo como uma lista de adjacência: um mapa de cada vértice para a lista de seus vizinhos. Isso torna a busca pelos vizinhos de um vértice um único acesso ao mapa, que é o que a maioria dos algoritmos de grafos precisa.

As operações que construiremos em nossa classe Graph são:

1. addVertex: Adiciona um novo vértice ainda sem arestas.
2. addEdge: Conecta dois vértices.
3. hasEdge: Verifica se dois vértices estão conectados.
4. getNeighbors: Obtém a lista de vizinhos de um vértice.
5. removeEdge: Desconecta dois vértices.
6. size: Conta quantos vértices o grafo possui.

Vamos construir uma classe Graph!