Os grafos podem modelar pontos turísticos dentro de uma região e as rotas para chegar nos pontos turísticos. Um parque quer construir vias pavimentadas para chegar a cada uma de suas atrações: lago, parquinho infantil, área de corrida, quadras poliesportivas e assim por diante, mas que o trecho pavimentado seja o mais curto possível, mas sem criar ciclos. O grafo abaixo modela o parque. Os valores nas arestas correspondem à distância entre os pontos turísticos do parque. Assinale a alternativa que corresponde ao algoritmo aplicado e valor do custo mínimo.

O enunciado pede construir vias para chegar a cada atração com trecho total o mais curto possível e sem criar ciclos. Isso caracteriza exatamente o problema da Árvore Geradora Mínima (AGM) em um grafo não orientado e ponderado. Os algoritmos clássicos para AGM são Prim ou Kruskal (Dijkstra é para menor caminho a partir de uma origem, não para conectar todos os nós com custo total mínimo).

Vamos calcular o custo mínimo (Kruskal): ordenar arestas por peso e ir escolhendo as menores que não formem ciclo.

Arestas (peso):

• $5$: $B\!- G$, $F\!- G$
• $10$: $A\!- B$, $A\!- D$, $E\!- G$
• $20$: $B\!- D$, $B\!- E$, $D\!- E$
• $40$: $A\!- F$, $G\!- H$
• $50$: $E\!- H$
• $70$: $F\!- H$

Seleção (evitando ciclos):

1. $B\!- G$ (5)
2. $F\!- G$ (5)
3. $A\!- B$ (10)
4. $A\!- D$ (10)
5. $E\!- G$ (10) Até aqui conectamos $A,B,D,E,F,G$.
6. Para incluir $H$, a menor aresta que o liga à árvore é $G\!- H$ (40) (melhor que $E\!- H=50$ e $F\!- H=70$).

Total: $5+5+10+10+10+40 = 80$.

Logo, o algoritmo adequado é Prim ou Kruskal, e o custo mínimo é 80.

Alternativa correta: (D).