Grafos
Grafos
- Um grafo é um conjunto de nós (também chamados vértices) ligados por arestas (conexões).
- Gráficos modelam redes: amigos, estradas entre cidades, links entre páginas da web.
- Uma árvore é realmente um grafo especial; um grafo geral pode ter ciclos e muitas ligações por nó.
Representando um grafo: lista de adjacência
- Uma forma comum é uma lista de adjacência: um dicionário que mapeia cada nó para sua lista de vizinhos.
graph["A"]é a lista de nós diretamente conectados aA.- Isso é compacto quando cada nó tem poucas conexões.
# A graph as a dict: each node maps to its list of neighbours
graph = {
"A": ["B", "C"],
"B": ["A"],
"C": ["A"],
}
print(graph["A"]) # ['B', 'C'] -- A connects to B and C
print(graph["B"]) # ['A']
Adicionar uma aresta
- Em um grafo não direcionado, uma aresta
A—Bvai nos dois sentidos. - Então adicioná-la significa appending
Bà lista deAeAà lista deB. - Se um nó for novo, inicie-o primeiro com uma lista vazia.
def add_edge(graph, a, b):
if a not in graph:
graph[a] = []
if b not in graph:
graph[b] = []
graph[a].append(b)
graph[b].append(a)
graph = {}
add_edge(graph, "A", "B")
add_edge(graph, "A", "C")
print(graph) # {'A': ['B', 'C'], 'B': ['A'], 'C': ['A']}
Percorrendo os vizinhos
- Para explorar a partir de um nó, você lê sua lista de vizinhos e visita cada um.
- Um nó que não está no grafo não tem nenhum vizinho — retorne uma lista vazia, não um erro.
- Essa consulta de vizinho é o primeiro passo de tarefas maiores como buscar todo o grafo.
Direcionado vs não direcionado
- Em um grafo não direcionado uma aresta funciona nos dois sentidos (uma amizade).
- Em um grafo direcionado uma aresta aponta apenas para um sentido (uma rua de mão única, um link "seguir").
- Para arestas direcionadas você faria o append apenas em um sentido.
Erros comuns
- Um grafo são nós ligados por arestas; uma aresta pode ser de um ou dois sentidos.
- Uma árvore é um grafo sem ciclos — não confunda os dois.
Agora você tenta
- Construa as operações da lista de adjacência:
add_edge,neighboursecount_edges. - Cada tarefa verifica sua função em um pequeno grafo.
- Pressione Check answer para testá-lo.
Dificuldade 5/5 · Moedas 400 + pequeno bônus na primeira conclusão hoje
Escreva add_edge(graph, a, b) para um grafo não direcionado armazenado como um dicionário de listas de vizinhos. Adicione b a graph[a] e a a graph[b]. Se um nó ainda não estiver no grafo, crie primeiro uma lista vazia []. Altere o dicionário in loco.
Clique em Executar para ver a saída aqui.
Dificuldade 5/5 · Moedas 400 + pequeno bônus na primeira conclusão hoje
Escreva neighbours(graph, node) que retorna a lista de nós diretamente conectados a node. Se node não estiver no grafo, retorne uma lista vazia [] (não levante erro).
Clique em Executar para ver a saída aqui.
Dificuldade 5/5 · Moedas 400 + pequeno bônus na primeira conclusão hoje
Escreva count_edges(graph) para um grafo não direcionado: conte quantas arestas ele tem. Some os comprimentos de cada lista de vizinhos, depois divida por 2 (cada aresta é armazenada nas listas de ambos os nós). Exemplo: um triângulo A–B–C tem 3 arestas.
Clique em Executar para ver a saída aqui.