Grafos e procura de caminhos — Informática, 14–17
Um grafo representa coisas e as ligações entre elas. Quando um problema é desenhado desta forma, um computador pode explorar rotas, ligações ou dependências, em vez de tratar cada situação como um caso especial.
Coisas e ligações
Num grafo, um vértice representa uma coisa e uma aresta representa uma relação ou rota entre coisas. As cidades podem ser vértices e as estradas, arestas; as pessoas podem ser vértices e as amizades, arestas. As arestas podem ter direção ou peso, como uma viagem de sentido único ou uma distância em quilómetros.
Por que desenhar um grafo?
Muitos problemas reais são, na verdade, problemas de ligações: entregar encomendas, encaminhar mensagens, sugerir amigos ou ordenar tarefas com pré-requisitos. Listas de factos isolados escondem essas ligações. Os grafos dão ao computador uma forma comum para estes problemas, permitindo usar um método em estradas, sítios Web ou dependências.
Escolher a rota mais curta
Suponhamos que A liga a B em 4 km, A a C em 1 km, C a B em 2 km e B a D em 3 km. De A para B, a rota direta tem 4 km, mas A–C–B tem 1 + 2 = 3 km, por isso é mais curta. De A para D passando por C e B, o total é 1 + 2 + 3 = 6 km.
Menos passos nem sempre é o caminho mais curto
É natural contar apenas quantas ligações uma rota usa: duas estradas parecem melhores do que três. Mas as ligações podem ter comprimentos, atrasos ou preços muito diferentes. Uma rota com três arestas de 1 km pode ganhar a uma rota com duas arestas de 10 km, por isso o grafo deve registar a quantidade que realmente interessa.
Grafos fora da sala de aula
As aplicações de navegação usam grafos de estradas com distâncias e tempos de trânsito. As plataformas sociais usam grafos de contas e relações, enquanto uma pesquisa na Web pode seguir ligações entre páginas. Em cada caso, o resultado depende do que conta como ligação e do peso importante: distância, tempo, custo ou relevância.
Continua a explorar
Outras línguas
A carregar o MyLeoNes™…