Introdução a grafos

Neste artigo introduzimos os conceitos base e a motivação de usar grafos para resolver problemas. Um grafo não é mais que uma estrutura matemática que abstrai um conjunto de entidades e as suas relações. Vamos decifrar esta definição nas próximas secções.

Motivação

Podemos ver grafos em várias situações e problemas, tanto de concursos como em vários domínios da ciência de computadores. Quando nos apresentam um conjunto de objetos, por exemplo cidades de um país, e nos indicam relações importantes entre esses objetos, por exemplo estradas entre as cidades, podemos abstrair este sistema como um grafo. Assim, é possível pensar em termos do objeto matemático e aplicar um conjunto de algoritmos e técnicas conhecidas para extrair a informação pedida pelo problema.

Para contextualizar a importância deste tema, desde 2005 que em todas as edições da IOI que aparece pelo menos um problema relacionado com grafos, aumentando esse número para pelo menos dois problemas a partir de 2006. Em termos de ONIs os números não são tão drásticos, mas é muito comum aparecerem problemas de grafos nas várias provas de uma edição das ONI.

Definição

Começamos por definir um grafo, dando alguns exemplos visuais de grafos assim como encontrar grafos em problemas algorítmicos. Além disso, veremos variações da definição de grafos que contabilizam elementos extra no grafo de modo a incluir mais informação (por exemplo, se incluirmos direção nas relações entre objetos podemos modelar estradas que tenham apenas um sentido. O próximo artigo resume todos estes conceitos (até à secção "Graph Representation"):

Agora que já têm uma ideia base do que é um grafo, podem explorar visualmente criar grafos e ver diferentes tipos de grafos usando a seguinte ferramenta:

Representações de grafos

Já sabemos então o que é um grafo e já temos uma intuição gráfica do que é um grafo, mas vamos passar a algo mais prático e representar grafos em código. Há várias maneiras diferentes de o fazer, tendo como objetivo suportar diferentes operações com maior eficiência. Assim, iremos considerar duas das mais importantes: uma lista de adjacências e uma matriz de adjacências. Voltemos ao artigo inicial e agora consideremos a sua segunda parte (a partir da secção "Graph Representation"):

Neste artigo também pudemos ver representações como listas de arestas, que são úteis em certos casos. Também muito importante é o caso dos grafos implícitos: se o grafo está representado de alguma forma nos nossos dados (uma grelha por exemplo) e é fácil de o atravessar (ou seja, seguir as suas arestas), então não vale a pena criar um grafo explícito além do input que temos. É importante saber quando usar cada representação, mas à medida que virmos algoritmos e usos para grafos, as melhores representações serão mais fáceis de detetar.

Sumário e recursos extra

Vimos então o que são grafos. Estas estruturas permitem-nos abstrair conjuntos de elementos com relações (cidades e estradas, amigos e amizades, ...). Vimos ainda algumas variações de grafos, por exemplo grafos com direção nas arestas. Posteriormente vimos como representar grafos em programação, através de diferentes estruturas que incluem toda a informação contida num grafo de formas diferentes. Um exercício importante agora seria implementar estes conceitos em código mesmo (usem a linguagem que sabem ou que preferem dentro das que sabem).

Para terem um reforço destes conceitos assim como alguns exemplos de implementações em pseudocódigo (uma linguagem de programação fictícia usada para representar código genericamente para todas as linguagens), recomendamos o próximo artigo (que contém ainda alguns tipos particulares interessantes de grafos):

O que se segue

Podem já ter reparado que esta secção não incluiu nenhum problema a resolver. Isto porque até agora só aprendemos a modelar problemas em grafos, mas ainda não sabemos usá-los para nada em concreto. Durante os próximos artigos iremos ver alguns algoritmos a aplicar em grafos, por exemplo percorrer grafos para encontrar componentes conexas, calcular o caminho mais curto (seguindo as arestas) entre dois elementos, entre outros algoritmos. Ai terão problemas suficientes para se entreterem.