Módulo Grafos

Neste módulo iremos ver todos os conceitos base importantes sobre grafos em problemas de programação. Problemas que usem grafos são ubíquos em concursos de programação e por isso é importante ter uma base sólida na sua teoria base para poder atacar esse tipo de problema.

Iremos passar por temas incrementalmente, vendo primeiro o que é e como representar um grafo, como pesquisar e retirar algumas propriedades de um grafo, e finalmente como trabalhar com pesos nas arestas de um grafo para extrair caminhos mais curtos e estruturas semelhantes.

Os vários artigos têm problemas de um modo geral simples e rápidos de se implementar. Se sentirem que não têm a certeza como implementar um certo conceito e/ou não perceberam alguma implementação que viram, sugerimos que os tentem resolver. Caso contrário, se se sentirem confiantes, experimentem alguns dos problemas dos artigos e alguns dos problemas de consolidação em baixo.

Artigo: Introdução a grafos

Neste artigo introduzimos o conceito de grafo e mostramos como o representar com código.

Artigo: Algoritmos em grafos simples

Passamos a ver como pesquisar e iterar num grafo de modo a ver algumas propriedades estruturais de qualquer grafo.

Artigo: Algoritmos em grafos pesados

Terminamos com um artigo sobre grafos com pesos nas arestas.

Para quem não conhecia o conceito de grafo ou nunca tinha aprendido os conceitos a fundo, devem-se lembrar de um problema que tinha uma estrutura de grafo como centro do problema, nomeadamente o Harmonia entre Nações, da final das ONI deste ano. Mesmo conhecendo estes conceitos o problema não é trivial, mas agora é mais fácil perceberem e tentarem resolver o problema.

Problemas de consolidação

Este conjunto de problemas é constituído por alguns problemas extra um pouco mais difíceis, mas que resumem bem a maioria dos tópicos dos artigos.

Nota: A fonte dos problemas representa a plataforma de submissão (todos são submetiveis) e não o concurso onde apareceu.