DS & II

Capítulo 14 - Grafos: Vértices e Arestas

Leitura de 3 min

🚀 Capítulo 14: Grafos: Vértices e Arestas (Tema: Game of Thrones)

NOTE

Este capítulo utiliza a temática de Game of Thrones para explicar os Grafos. As cidades de Westeros e as alianças entre as famílias formam uma rede complexa de conexões!

1. 🎯 Objetivo da Aula

Compreender o conceito de Grafo como estrutura de dados não-linear, identificando Vértices (Nós) e Arestas (Conexões), além de entender a diferença entre grafos direcionados e não-direcionados.

2. 🏢 O Cenário Prático (Seu Desafio)

O Meistre da Cidadela precisa mapear o continente de Westeros para planejar as rotas dos corvos mensageiros.

  • Temos as cidades (Porto Real, Winterfell, Rochedo Casterly).
  • Temos as estradas que ligam essas cidades.

Além disso, ele quer mapear as relações de aliança:

  • A Casa Stark é aliada da Casa Tully (Mão dupla).
  • Mas a Casa Frey finge ser aliada e ataca os Stark (Mão única/Traição!).

Essa rede de cidades/casas e estradas/alianças é um Grafo. Seu desafio é entender como estruturar essa teia de relações!

3. 🧠 Fundamentos: A Teoria Traduzida

Um Grafo é a estrutura de dados mais flexível que existe. Ela é composta por dois elementos:

  1. Vértices (ou Nós): São os pontos da rede (Ex: As cidades ou as famílias).
  2. Arestas: São as linhas que conectam os pontos (Ex: As estradas ou as alianças).

➡️ 1. Grafos Direcionados vs Não-Direcionados

  • Não-Direcionado: A conexão não tem sentido obrigatório. Se existe estrada entre Winterfell e Porto Real, você pode ir e voltar. A linha não tem seta.
  • Direcionado (Dígrafo): A conexão tem um sentido. Ex: Um rio que só corre para um lado, ou um seguidor no Instagram (Você segue o Jon Snow, mas ele não te segue). A linha tem seta.

💰 2. Grafos Valorados (Com Peso)

As arestas podem ter um valor (custo). Ex: A distância em km entre as cidades.

4. 📖 Exemplo Guiado: O Mapa de Alianças

graph TD
    Stark((Stark)) <--> Tully((Tully))
    Stark -->|Traição| Frey((Frey))
    Lannister((Lannister)) --- Baratheon((Baratheon))
  • Stark e Tully têm uma aresta não-direcionada (aliança mútua).
  • Stark para Frey tem uma aresta direcionada (seta).

5. 🛠️ Prática Obrigatória 1: Contando Elementos

Com base no exemplo guiado:

  1. Quantos Vértices existem no grafo?
  2. Quantas Arestas existem no grafo?
  3. Qual Casa não tem nenhuma ligação com os Stark no diagrama?

6. 🛠️ Prática Obrigatória 2: Redes Sociais

Pense no Facebook e no Instagram.

  1. No Facebook, para ser amigo, os dois precisam aceitar. Esse grafo é Direcionado ou Não-Direcionado?
  2. No Instagram, você pode seguir alguém sem que a pessoa te siga. Esse grafo é Direcionado ou Não-Direcionado?

7. 📤 Instruções de Entrega (GitHub Desktop + Microsoft Teams)

  1. Faça o Commit: No GitHub Desktop, digite a mensagem (ex: Finaliza Capítulo 14 Estruturas de Dados) e clique em Commit to main.
  2. Envie para a Nuvem (Push): Clique em Push origin.

8. 📂 Estrutura de Pastas

mod_09_estruturas_de_dados/
├── capitulos/
│   ├── capitulo_14_grafos.md
│   └── codigos/
│       └── cap14/
│           └── mapa_westeros.txt

9. 💡 Checkpoint de Lógica

Toda Árvore (como as que vimos nos capítulos anteriores) é um Grafo? E todo Grafo é uma Árvore? (Dica: Árvores não podem ter ciclos, ou seja, caminhos que voltam para o mesmo lugar).

10. 🔥 Desafio de Fixação

Pesquise o que é uma Matriz de Adjacência e como ela é usada para representar grafos no código.

🔑 Gabarito de Código/Fórmulas

Gabarito da Prática 1:

  1. 5 Vértices (Stark, Tully, Frey, Lannister, Baratheon).
  2. 3 Arestas (Stark-Tully, Stark-Frey, Lannister-Baratheon).
  3. As Casas Lannister e Baratheon não têm ligação com os Stark.

← Capitulo Anterior | Proximo Capitulo →

Visão de gráfico

Backlinks