Pular para o conteúdo

O básico de grafos

Aula 1 de 16 · 5 min

O básico de grafos

Passo 1 de 7

Um grafo é coisas mais as conexões entre elas. Essa é a definição inteira.

A ideia

Um grafo é feito de nós ligados por arestas. Essa é a definição inteira — arrays e listas encadeadas (linked lists) só acrescentam regras por cima dela. As arestas podem ser não direcionadas (uma ligação de mão dupla) ou direcionadas (mão única). O grau de um nó é simplesmente quantas arestas tocam nele.

Exemplo do mundo real

Uma molécula é um grafo que você pode segurar na mão. Os átomos são os nós, as ligações químicas são as arestas e, quando todas as ligações são simples, a valência de um átomo é o grau dele: o carbono aceita quatro ligações, o hidrogênio exatamente uma. Químicos desenham estruturas em vez de fórmulas porque são as conexões, e não a contagem de átomos, que decidem o que a substância faz.

O código

Sua vez

O que isto imprime?

g = {"A": ["B", "C"], "B": ["A"], "C": ["A"]}
print(len(g), sum(len(v) for v in g.values()) // 2)

Mini quiz

1 / 3

Quais são os dois ingredientes de todo grafo?