Um grafo G = (V, E) é um conjunto de vértices (V, os objetos) ligados por arestas (E, as relações entre pares de objetos).

Listas e árvores são casos particulares de grafos. A diferença é que, num grafo geral, qualquer vértice pode se ligar a qualquer outro, inclusive formando ciclos.

Uma matriz V × V em que m[u][v] = 1 se existe a aresta u–v (ou o peso dela, num grafo ponderado), e 0 caso contrário.

• Existe a aresta u–v? Basta olhar m[u][v]: O(1).
• Quais os vizinhos de v? Percorre a linha toda: O(V), mesmo que v tenha 1 vizinho.
• Memória: V² posições, sempre.

Num grafo não dirigido a matriz é simétrica: m[u][v] == m[v][u].

Para cada vértice, uma lista só com os seus vizinhos. Em Python, um dict de listas (ou uma lista de listas, se os vértices forem 0, 1, …, V−1).

• Vizinhos de v: direto, O(grau de v). É o que os percursos mais usam.
• Existe u–v? Procura na lista de u: O(grau de u).
• Memória: O(V + E).

Num grafo ponderado, cada vizinho vira um par (vizinho, peso).

A maioria dos grafos reais é esparsa: cada vértice tem poucos vizinhos comparado com V. Uma rede com 1 milhão de pessoas e 100 amigos por pessoa teria uma matriz de 10¹² posições, quase todas zero.

Regra prática: lista de adjacência por padrão; matriz para grafos pequenos ou densos, ou quando a pergunta “existe u–v?” domina.

Formato usado nos exercícios desta aula (e em maratonas de programação):

• primeira linha: V E — número de vértices e de arestas;
• depois, E linhas u v (ou u v peso);
• os vértices são numerados de 0 a V − 1.

Como os vértices são números, uma lista de listas basta: g[u] é a lista de vizinhos de u.

1. Coloque a origem na fila com distância 0.
2. Enquanto a fila não estiver vazia, tire o primeiro vértice v.
3. Para cada vizinho w ainda não descoberto: dist[w] = dist[v] + 1 e w entra no fim da fila.

Cada vértice entra na fila uma vez e cada aresta é olhada uma vez (duas, se não dirigido): O(V + E).

A versão recursiva é a mais curta: visitar v é marcar v e chamar a DFS para cada vizinho não visitado. A pilha de chamadas do Python guarda o caminho de volta.

Em grafos grandes, a recursão pode estourar o limite do Python (cerca de 1000 chamadas). Aí trocamos a pilha de chamadas por uma pilha explícita (list com append/pop).

Um grafo pode estar dividido em “ilhas” sem ligação entre si: as componentes conexas.

Para encontrá-las, percorra a partir de cada vértice ainda não visitado. Cada novo percurso (BFS ou DFS, tanto faz) descobre uma componente inteira.

Apesar do laço sobre todos os vértices, cada vértice e cada aresta são tratados uma vez só no total: O(V + E).

Num grafo não dirigido, durante a DFS, encontrar um vizinho já visitado que não é o vértice de onde viemos significa que há dois caminhos até ele: existe um ciclo.

Por isso a pilha guarda pares (vértice, pai): a aresta de volta para o pai não conta como ciclo.

Uma árvore é justamente um grafo conexo sem ciclos. Ela tem sempre V − 1 arestas: uma a menos e ficaria desconexa, uma a mais e formaria um ciclo.

Na BFS, um vértice é descoberto pela primeira vez pelo caminho com menos arestas. Guardando quem descobriu cada vértice (o pai), dá para reconstruir esse caminho.

Para montar a rota até t, siga os pais de t até a origem e inverta a lista.

Funciona quando todas as arestas “custam” o mesmo: número de estações, de conexões entre pessoas, de cliques entre páginas.

Nem sempre o grafo aparece como lista de arestas. Num mapa em grade, cada casa livre é um vértice e seus vizinhos são as casas livres acima, abaixo, à esquerda e à direita.

Não precisamos montar a lista de adjacência: calculamos os vizinhos na hora, somando os deslocamentos (±1, 0) e (0, ±1) e conferindo se a casa existe e não é parede.

A BFS a partir do início espalha as distâncias como uma mancha de tinta (flood fill). O mapa impresso mostra, em cada casa, quantos passos ela está do S.

1. dist[s] = 0 e ∞ para os demais; a fila de prioridade começa com (0, s).
2. Tire o par de menor distância (d, u). Se d for maior que dist[u], é uma entrada antiga: ignore.
3. Para cada vizinho v com peso p: se dist[u] + p < dist[v], atualize e coloque (dist[v], v) na fila.

O heapq implementa a fila de prioridade (um heap, visto na aula de ordenação). Custo: O((V + E) log V).

1. Calcule o grau de entrada de cada vértice.
2. Coloque os de grau 0 em prontos.
3. Retire um pronto, acrescente-o à ordem e diminua o grau de entrada de cada vizinho; quem chegar a 0 fica pronto.
4. Se a ordem terminar com menos de V vértices, há um ciclo.

Pode haver várias ordens válidas. Usar um heapq em prontos escolhe sempre o menor número, deixando a resposta única. Custo: O(V + E), ou O((V + E) log V) com o heap.

No mapa, "1" é terra e "0" é água. Uma ilha é um grupo de terras ligadas na horizontal ou na vertical (diagonal não conta).

Conte quantas ilhas existem. Para o mapa ao lado, a resposta é 5.

É o problema das componentes conexas num grafo implícito em grade: para cada terra ainda não visitada, conte uma ilha nova e “pinte” toda a ilha com uma BFS ou DFS.