Graphs · Grafos
Graphs
- A graph is a set of nodes (also called vertices) joined by edges (connections).
- Graphs model networks: friends, roads between cities, links between web pages.
- A tree is really a special graph; a general graph can have cycles and many links per node.
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ó.
Representing a graph: adjacency list
- One common way is an adjacency list: a dictionary mapping each node to its list of neighbours.
graph["A"]is the list of nodes directly connected toA.- This is compact when each node has only a few connections.
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']
Adding an edge
- In an undirected graph, an edge
A—Bgoes both ways. - So adding it means appending
BtoA's list andAtoB's list. - If a node is new, start it with an empty list first.
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']}
Walking the neighbours
- To explore from a node, you read its neighbour list and visit each one.
- A node that is not in the graph has no neighbours — return an empty list, not an error.
- This neighbour lookup is the first step of bigger jobs like searching the whole graph.
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.
Directed vs undirected
- In an undirected graph an edge works both ways (a friendship).
- In a directed graph an edge points one way only (a one-way street, a "follows" link).
- For directed edges you would append in one direction only.
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.
Common mistakes
- A graph is nodes joined by edges; an edge can be one-way or two-way.
- A tree is a graph with no cycles — do not confuse the two.
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.
Now you try
- Build the adjacency-list operations:
add_edge,neighbours, andcount_edges. - Each task checks your function on a small graph.
- Press Check answer to test it.
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.
Write add_edge(graph, a, b) for an undirected graph stored as a dict of neighbour lists. Append b to · até graph[a] and · e a to · até graph[b]. If a node is not in the graph yet, give it an empty list [] first. Change the dict in place. · 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.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Write neighbours(graph, node) that returns the list of nodes directly connected to node. If node is not in the graph, return an empty list [] (do not raise an error). · 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).
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Write count_edges(graph) for an undirected graph: count how many edges it has. Add up the lengths of every neighbour list, then divide by 2 (each edge is stored in both nodes' lists). Example: a triangle A–B–C has 3 edges. · 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.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.